【复习】最小生成树 Kruskal

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者经典模版#includeiostream #includevector #includealgorithm using namespace std; typedef struct node { int u, v, w; }node; vectornodeedges; vectorintparent; bool f(node a, node b) { return a.w b.w; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } int main() { int N, M; cin N M; edges.resize(M); parent.resize(N1); for (int i 1; i N; i) { parent[i] i; } for (int i 0; i M; i) { cin edges[i].u edges[i].v edges[i].w; } sort(edges.begin(), edges.end(), f); long long sum 0; long long use 0; for (int i 0; i M; i) { int rootu find(edges[i].u); int rootv find(edges[i].v); if (rootu ! rootv) { use; sum edges[i].w; parent[rootu] rootv; if (use N - 1) break; } } if (use N - 1) { cout sum endl; } else cout orz endl; return 0; }需要注意的是find函数返回的是parent[x]而不是x;中间那个是findparent[x];做题做题#includeiostream #includevector #includealgorithm using namespace std; typedef struct node { int u, v, w; }node; bool f(node a, node b) { return a.w b.w; } vectorintparent; vectornodearr; int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } int main() { int A, B; cin A B; parent.resize(B 1); for (int i 1; i B; i) { parent[i] i; } for (int i 1; i B; i) { arr.push_back({ 0,i,A }); } for (int i 1; i B; i) { for (int j 1; j B; j) { int k; cin k; if (i j k0) { arr.push_back({ i,j,k }); } } } sort(arr.begin(), arr.end(), f); long long sum 0; long long use 0; for (int i 0; i arr.size(); i) { int u arr[i].u; int v arr[i].v; int w arr[i].w; int rootu find(u); int rootv find(v); if (rootu ! rootv) { parent[rootu] rootv; sum w; use; if (use B) { break; } } } cout sum endl; }这个非常有意思刚开始根本没看出是最小生成树但是现在一想他这个还是那个样式就是这个礼物和另外一个礼物之间有个权值就像一个节点和一个节点之间的权值是一样的然后这个有个不一样那个的地方他有个初始化的价格就是这个价格不受任何别的物品的影响这个咱们就当做是节点0和当前节点之间的权值然后把他们全部加进一个数组按照那个权值w排序找出最小的一个个并查集加入然后就是可能会有疑问诶这个0明明是自己创建的虚拟节点为什么也要加入并查集假如0,2买过了遇到1,2还会再次购买吗问的很好so nace首先0必须要加入虚拟节点的咱们举个例子假如0,2也就是原价更加便宜先把原价买了0,2现在在同一个并查集了然后因为原价不是便宜吗哈哈哈所以下一个要遍历的还是0X这种然后才到1,2也就是0,1肯定子啊1,2前面0,1之后0和1就在一个并查集了而0,2也在所以1,2就在一个并查集了所以1,2不会被购买