0412备战蓝桥杯，图论复习

本文主要是介绍0412备战蓝桥杯，图论复习，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.朴素dijkstra

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 510; int n,m;
int g[N][N],dist[N];
bool st[N];int dij(){memset(dist,0x3f,sizeof dist);dist[1] = 0;for(int i=0;i<n;i++){//n次迭代 int t = -1;for(int j=1;j<=n;j++)if(!st[j] && (t == -1 || dist[j] < dist[t])) t=j;st[t] = true;for(int j=1;j<=n;j++){dist[j] = min(dist[j],dist[t]+g[t][j]);} }if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
int main()
{cin>>n>>m;memset(g,0x3f,sizeof g);for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b] = min(g[a][b],c);}int t = dij();cout<<t<<endl;return 0;
}

2.floyd：初始化自己到自己是0

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 210; int n,m,k;
int e[N][N];
int st[N];void floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){e[i][j] = min(e[i][j],e[i][k]+e[k][j]);}}}return ;
}int main(){cin>>n>>m>>k;//memset(e,0x3f,sizeof e);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) e[i][j] = 0;else e[i][j] = 0x3f3f3f3f;}}while(m--){int a,b,c;cin>>a>>b>>c;e[a][b] = min(e[a][b],c);}floyd();while(k--){int x,y;cin>>x>>y;if(e[x][y] > 0x3f3f3f3f/2) cout<<"impossible"<<endl;else cout<<e[x][y]<<endl;}return 0;
}

3.prim：点到集合的距离

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 510; int e[N][N];
int st[N];
int dist[N];//点到集合的距离 
int n,m;
int res;
int cnt;int prim(){memset(dist,0x3f,sizeof dist);for(int i=0;i<n;i++)//n次迭代{int t=-1;for(int j=1;j<=n;j++){if(!st[j] && (t==-1 || dist[j]<dist[t])){t=j;}}if(i && dist[t] == 0x3f3f3f3f){return 0x3f3f3f3f;//一定要返回无穷大1，不然-1也有可能是答案}if(i) res+=dist[t];st[t] = true;/*	st[t] = true;cnt++;res+=dist[t];*/for(int j=1;j<=n;j++){//用t更新点到集合的距离dist[j] = min(dist[j], e[t][j]); }} return res;
}
int main()
{cin>>n>>m;memset(e,0x3f,sizeof e);while(m--){int u,v,w;cin>>u>>v>>w;if(u==v) continue;e[u][v] = e[v][u] = min(e[v][u],w);}	if(prim() == 0x3f3f3f3f) cout<<"impossible"<<endl;else cout<<prim()<<endl;return 0;
}

4.kruskal：选取最小边进入集合，注意并查集p[x] = find(p[x])

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 200010; 
//kruskal从最短边加入集合
int p[N];
int n,m;
struct node{int u,v,w;
}; 
node e[N];
int res,cnt;bool cmp(node aa,node bb){return aa.w < bb.w;
}int find(int x){if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++) p[i]=i;for(int i=1;i<=m;i++){int u,v,w;//	if(u==v) continue;cin>>u>>v>>w;e[i] = {u,v,w};}	sort(e+1,e+m+1,cmp);//枚举每条边 for(int i=1;i<=m;i++){int u=e[i].u;int v=e[i].v;int w=e[i].w;u=find(u);v=find(v);if(u!=v){//如果不在一个连通块res += w;cnt++;p[u] = v;//加入集合 } }if(cnt<n-1) cout<<"impossible"<<endl;else cout<<res<<endl; return 0;
}