图论--最小生成树

prim算法(稠密图)例题:https://www.acwing.com/problem/content/860/给定一个 n 个点 m 条边的无向图图中可能存在重边和自环边权可能为负数。求最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G(V,E)其中 V 表示图中点的集合E 表示图中边的集合n|V|m|E|。由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。输入格式第一行包含两个整数 n 和 m。接下来 m 行每行包含三个整数 u,v,w表示点 u 和点 v 之间存在一条权值为 w 的边。输出格式共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。数据范围1≤n≤500,1≤m≤105,图中涉及边的边权的绝对值均不超过 10000。输入样例4 51 2 11 3 21 4 32 3 23 4 4输出样例6#include iostream#include algorithm#include cstringusing namespace std;const int N 510,INF 0x3f3f3f3f;int n,m;int arr[N][N],dist[N];bool st[N];int prim(){memset(dist,0x3f,sizeof dist);int ans 0;dist[1] 0;for(int i 1;i n;i){int t -1;for(int j 1;j n;j){if(!st[j] (t -1 || dist[t] dist[j]))t j;}ans dist[t];if(dist[t] INF) return INF;st[t] true;for(int j 1;j n;j){dist[j] min(dist[j],arr[t][j]);}}return ans;}int main(){cin n m;memset(arr,0x3f,sizeof arr);for(int i 1;i m;i){int x,y,z;cin x y z;arr[x][y] arr[y][x] min(z,arr[x][y]);}int res prim();if(res INF) cout impossible endl;else cout res endl;return 0;}算法核心:从不在st集合当中的点选择一个距离st集合中点最近的点加入到st当中 并用此点来更新不在st集合中点到st集合的距离需要注意的是与之前图论的问题不同 这里的dist数组指的是此节点到已经建好的生成树的距离 而不是到某个点的距离通过枚举修改dist数组来不断更新未加入到集合中节点到集合的距离每次选取最短距离则可以建成最小生成树Kruskal算法(稀疏图)例题:https://www.acwing.com/problem/content/861/给定一个 n 个点 m 条边的无向图图中可能存在重边和自环边权可能为负数。求最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G(V,E)其中 V 表示图中点的集合E 表示图中边的集合n|V|m|E|。由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。输入格式第一行包含两个整数 n 和 m。接下来 m 行每行包含三个整数 u,v,w表示点 u 和点 v 之间存在一条权值为 w 的边。输出格式共一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。数据范围1≤n≤105,1≤m≤2∗105,图中涉及边的边权的绝对值均不超过 1000。输入样例4 51 2 11 3 21 4 32 3 23 4 4输出样例6#include iostream#include cstring#include algorithmusing namespace std;const int N 1e5 10,M 2e5 10,INF 0x3f3f3f3f;int n,m,p[N],ans,cnt;int find(int x){if(p[x] ! x) p[x] find(p[x]);return p[x];}struct Edge{int a,b,w;bool operator (const Edge W) const{return w W.w;}}edge[M];void Kruskal(){for(int i 1;i m;i){auto t edge[i];int a t.a,b t.b,w t.w;a find(a),b find(b);if(a ! b){ans w;cnt;p[a] b;}}}int main(){cin n m;for(int i 1;i n;i){p[i] i;}for(int i 1;i m;i){int x,y,z;cin x y z;edge[i] {x,y,z};}sort(edge 1,edge m 1);Kruskal();if(cnt n - 1) cout ans endl;else cout impossible endl;return 0;}算法核心:使用并查集来维护节点是否在同一个集合内部若是选到的边两边的节点在一个集合内部则跳过此边 选择下一条边继续判断关键点 创建一个结构体数组来存储边的信息sort排序并依次取出权值最小的边