今天看啊哈算法最小生成树 Kruskal算法，然后写问题
也就是说，边缘按权重排序，然后从小到大选择边缘的两个顶点，看看它们是否会形成一个环，以确保每个边缘都是最小的，这里可以使用和收集合并，判断它是否会形成一个环，循环这个过程，然后直到找到N-到目前为止，如果没有那么多条边，就不会连接
题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出
orz。输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出
orz。输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3复制
7说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
Kruskal算法
#include<bits/stdc .h> using namespace std; const int n = 200001; int N, M; int f[n]; struct node{ int a, b, v; }eg[n]; bool cmp(node w, node e) { return w.v < e.v; } int getf(int q) { if(f[q] == q) return q; else return getf(f[q]); } int Merge(int w,int e) { int t1 = getf(w); int t2 = getf(e); if(t1 != t2){ f[t1] = t2; return 1; } else return 0; } int main() { cin >> N >> M; for(int i = 1; i <= N; i ) f[i] = i; int sum = 0, t = 0; for(int i = 1; i <= M; i ) cin >> eg[i].a >> eg[i].b >> eg[i].v; sort(eg 1, eg M 1, cmp); for(int i = 1; i <= M; i ){ if(Merge(eg[i].a, eg[i].b)){ sum = eg[i].v; t ; } if(t == N-1) break; } if(t == N-1) cout << sum << endl; else cout << "orz" << endl; // for(int i = 1; i <= M; i ) // cout << eg[i].a << eg[i].b << eg[i].v << endl; return 0; }P2121 拆地毯
Kruskal算法，它需要最大值，从大到小排序
#include<bits/stdc .h> using namespace std; const int N = 100001; int n, m, k; int f[N]; struct node{ int a, b, v; }eg[N]; bool cmp(node a, node b) { return a.v > b.v; } int getf(int v){ if(f[v] == v) return v; else{ f[v] = getf(f[v]); return f[v]; } } int Merge(int w, int e) { int t1 = getf(w); int t2 = getf(e); if(t1 != t2){ f[t1] = t2; return 1; } else return 0; } int main() { cin >> n >> m >> k; for(int i = 1; i <= m; i ){ cin >> eg[i].a >> eg[i].b >> eg[i].v; } sort(eg 1, eg m 1,cmp); int sum = 0, t = 0; for(int i = 1; i <= n; i ) f[i] = i; for(int i = 1; i <= n; i ){ if(Merge(eg[i].a, eg[i].b)){ sum = eg[i].v; t ; } if(t == k) break; } cout << sum << endl; }P1195 口袋的天空
还是Kruskal算法
#include<bits/stdc .h> using namespace std; const int n = 100010; int N, M, K; int f[n]; struct node{ int a, b, v; }eg[n]; bool cmp(node a, node b) { return a.v < b.v; } int getf(int w) { if(f[w] == w) return w; else return getf(f[w]); } int Merge(int w, int e) { if(getf(w) != getf(e)){ f[getf(w)] = getf(e); return 1; } else return 0; } int main() { cin >> N >> M >> K; for(int i = 1; i <= N; i ) f[i] = i; for(int i = 1; i <= M; i ){ cin >> eg[i].a >> eg[i].b >> eg[i].v; } sort(eg 1, eg M 1, cmp); int sum = 0, t = 0; for(int i = 1; i <= M; i ){ if(Merge(eg[i].a, eg[i].b)){ sum = eg[i].v; t ; } if(t == N - K) break; } if(t == N - K) cout << sum << endl; else cout << "No Answer" << endl; return 0; }