# 图论 ## 最短路 ### Floyd算法 用于寻找**所有点到所有点**的最短距离。使用邻接矩阵存图，枚举每个点作为中转点，不断更新a[ i ] [ j ]中的最短距离。复杂度为**O(o^3)**可以过两百的数据.**不能解决负权回路最短路**。 ```c++ void floyd(){//f[i][j]表示从i到j的最短距离，初始要全赋成正无穷 for(int k=1;k<=n;k++){//k表示枚举中转点 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } } } } ``` 使用动态规划实现，结果为f[ n ] [ x ] [ y ]。第一维无影响可以省略变为上述结果。k为前k个结点作为中转点。 ```c++ void floyd(){ for(int k=1;k<=n;k++){ for(int x=1;x<=n;x++){ for(int y=1;y<=n;y++){ f[k][x][y]=min(f[k-1][x][y],f[k-1][x][k],f[k-1][k][y]); } } } } ``` ### Bellman_Ford算法 计算**一个点到其他点**的最短距离。边的权值**可以为负数**，并**可检测负权回路**。时间复杂度为**O(n\*m)**节点数×边数。 多次遍历每一个点，更新两点间最短路径。 ```c++ vector<pair<int,int> > adj[1000];//用邻接表实现，first 存是指向的点，second存距离 int dis[1000]; int n; void bellman(int st){ for(int i=1;i<=n;i++){ dis[i]=inf; } dis[st]=0; int flag,ans=0; for(int t=1;t<=n;t++){//最多循环n-1次，以此判断负圈 flag=0; for(int i=1;i<=n;i++){ for(int j=0;j<adj[i].size();j++){ int v = adj[i][j].first; int d = adj[i][j].second; if(dis[v]>dis[i]+d){ dis[v=dis[i]+d; flag=1; } } } if(flag==1&&t==n) ans=true;//如果第n次也进行更新，则存在负圈 if(!flag) break;//如果这次没有点进行松弛操作则dis中存的已是最短路径 } } ``` ### SPFA算法 算是**bellman的优化**，用队列实现，经过松弛操作的点才会进入队列，经行下一轮最短路的更新。边的权值**可以为负数**，并**可检测负权回路**。时间复杂度为**O( K M )**,M可以看作是常数，最高是**O( N M )**。用于**疏密图**，稠密图用这个要考虑下。 ```c++ queue<int> que; vector<pair<int,int>>adj[500005]; int vis[100000],dis[100000],cnt[100000]; int n; void spfa(int s){ que.push(s); vis[s]=1; for(int i=1;i<=n;i++){ dis[i]=inf; } dis[s]=0; while(que.size()){ int u=que.front(); que.pop(); vis[u]=0; for(auto [v,d]:adj[u]){ if(dis[v]>dis[u]+d){ dis[v]=dis[u]+d; cnt[v]=cnt[u]+1; if(cnt[v]>=n){//判断负环 cout<<"No"; return; } if(vis[v]==0){ que.push(v); vis[v]=1; } } } } } ``` ### **Dijkstra算法** 计算**一个点到其他点**的最短距离。边权**不能为负**，**不可检测负权回路**。用贪心，每次去找离起点最近的点。可以用来**找路径**。 以下为朴素算法，用**邻接图**实现，**O(n^2)**的复杂度，可用于**稠密图**。 ```c++ int f[N][N],n,m,dis[N],vis[N]; void dj(int st){ for(int i=1;i<=n;i++){ dis[i]=inf; } dis[st]=0; for(int i=1;i<=n;i++){ int t=-1; for(int j=1;j<=n;j++){ if(!vis[j]&&(t=-1||dis[j]<dis[t])){ t=j; } } if(t==-1) return;//所有其他路都遍历过，vis满了 vis[t]=1;//贪心，找到即是最短 for(int j=1;j<=n;j++){ if(dis[j]>dis[t]+f[t][j]){ dis[j]=dis[t]+f[t][j];//去更新其他点到起点的距离，不需要vis判断 } } } } ``` 以下用优先队列优化和邻接表，时间复杂度为**O(mlog m)**，可用于**稀疏图**。 ```c++ const int N=1e5+5; itn n; int dis[N],vis[N],f[N]; vector<pair<int,int>>adj[N];//邻接表存图 priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que; void find(int n){//找路径 if(n==1){ cout<<1<<' '; return; } find(par[n]); cout<<n<<' '; } void dj(int st){ memest(dis,0x3f,sizeof(dis));//所有点到起点距离为无穷 que.push({dis[st]=0,st});//距离在前，先对距离排序 f[st]=1;//存st到该点最短路路径数 while(que.size()){ int x=que.top().second;//距离起点最小的点，贪心的思想，一定是起点到该点的最短路 que.pop(); if(vis[x]) continue;//别忘！ vis[x]=1;//防止队列中同一个点多次遍历。进过松弛的点一定只会去遍历一遍 for(auto [y,v]:adj[x]){//遍历连接x的所有边 if(dis[y]>dis[x]+v){ dis[y]=dis[x]+v; par[y]=x;//记录父亲节点用于找路径 f[y]=f[x];//最短路路径数没变 //if(vis[y]==0) 小优化 que.push({dis[y],y});//进行过松弛的要加入队列，继续更改 } else if(dis[y]==dis[x]+v){ f[y]+=f[x];//如果相等，就存在两条 } } } if(dis[n]!=inf) find(n); else cout<<-1;//没有路径就输出-1 } ``` ## 最小生成树 ### Kruskal算法 利用贪心思想，每次找最小的边，并且边上两点不在同一颗树内。复杂度为**O(MlogN)**或**O(MlogM)**。一般应该是后者。 ```c++ struct node{ int u,v,d; }adj[200010]; int par[200010]; bool cmp(node a,node b){ return a.d<b.d; } int find(int n){ if(par[n]==n)return n; return par[n]=find(par[n]);//并查集用法 } signed main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ cin>>adj[i].u>>adj[i].v>>adj[i].d; } sort(adj,adj+m,cmp); int ans=0,cnt=0; for(int i=1;i<=n;i++){ par[i]=i; } for(int i=0;i<m;i++){ if(find(adj[i].u)==find(adj[i].v)) continue; ans+=adj[i].d; par[adj[i].u]=adj[i].v; cnt++; } if(cnt==n-1)//树存在n-1条边 cout<<ans; else cout<<"orz"; } ``` ### Prim算法 用**邻接图**，一步步找未知点中与以确定的集合最近的点，dijkstra是找距离已知点最近的点，这点有点不同，复杂度是**O(N^2)**。 ```c++ const int inf=0x3f3f3f3f3f3f3f3f; int vis[200005],dis[200005],n,m,dist[200005]; int f[200005][200005]; void prim(){ for(int i=1;i<=n;i++){ dist[i]=inf;//存到集合的距离 } dist[1]=0; vis[1]=0; for(int i=2;i<=n;i++){ dist[i]=min(dist[i],f[1][i]); }//更新最短距 for(int i=2;i<=n;i++){ int temp=inf; int t=-1;//存下标 for(int j=2;j<=n;j++){ if(!vis[j]&&dist[j]<temp){//求未确定的最短距 temp=dist[j]; t=j; } } if(t==-1){//没有最小距离，即图不连通 res=inf; return; } vis[t]=1; res+=dist[t];//存总最小距离 for(int j=2;j<=n;j++){ dist[j]=min(dist[j],f[t][j]);//更新与t相连的点的最小距 } } } ``` 用优先队列和邻接表实现，复杂度为O(mlogm) ```c++ #include<bits/stdc++.h> using namespace std; #define int long long const int N = 110; int a[N][N]; int vis[N]; signed main(){ int n; cin >> n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cin >> a[i][j]; } } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que; int st = 1; for(int i = 1; i <= n; i++){ if(a[st][i]){ que.push({a[st][i], i}); } } int sum = 0; vis[st] = 1; while(que.size()){ int x = que.top().first; int y = que.top().second; que.pop(); if(vis[y]) continue; // cout << y << endl; sum += x; vis[y] = 1; for(int i = 1; i <= n; i++){ if(vis[i] == 0 && a[y][i] != 0){ que.push({a[y][i], i}); } } } cout << sum; } ``` ## 拓扑排序 有向无环图，好像是一层一层往下搜。使用队列实现。类似dp。 例子 [求食物链的条数。](https://www.luogu.com.cn/problem/P3183) ```cpp //链式前向星 struct node{ int next;//下一条边的下标 int to;//该条边指向的点 }; int cnt=-1; node edge[200010]; int head[100010];//以i为顶点的第一条边 void add_edge(int u,int v){ edge[++cnt].next=head[u];//给边标下标 edge[cnt].to=v;//该边指向的点 head[u]=cnt;//把头更新为最后加入的边的下标 } int deg[100010],dp[100010]; queue<int>que; signed main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ head[i]=-1; } for(int i=0;i<m;i++){ int u,v; cin>>u>>v; add_edge(u,v);//有向图的加边 //add_edge(v,u) 无向图存边，edge空间开两倍 deg[v]++;//记录入度 } for(int i=1;i<=n;i++){ if(deg[i]==0){ que.push(i);//入度为零，即无点指向它 } } int ans=0; while(!que.empty()){ int u=que.front(); que.pop(); for(int i=head[u];~i;i=edge[i].next){//~i为i！=-1，遍历以u为顶点的所有边 int v=edge[i].to; dp[v]+=(dp[u]==0?1:dp[u]);//如果是单独的点，就形成了一条链，不然加上链数 deg[v]--;//入度减减，实现一层层搜 if(deg[v]==0){ que.push(v); } } if(head[u]==-1){//该点没有出度 ans+=dp[u]; } } cout<<ans; } ```