洛谷P3366 【模板】最小生成树题解

1.原题和原题链接原题链接P3366 【模板】最小生成树题目描述如题给出一个无向图求出最小生成树如果该图不连通则输出orz。输入格式第一行包含两个整数N , M N,MN,M表示该图共有N NN个结点和M MM条无向边。接下来M MM行每行包含三个整数X i , Y i , Z i X_i,Y_i,Z_iXi​,Yi​,Zi​表示有一条长度为Z i Z_iZi​的无向边连接结点X i , Y i X_i,Y_iXi​,Yi​。输出格式如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出orz。输入输出样例 #1输入 #14 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3输出 #17说明/提示数据规模对于20 % 20\%20%的数据N ≤ 5 N\le 5N≤5M ≤ 20 M\le 20M≤20。对于40 % 40\%40%的数据N ≤ 50 N\le 50N≤50M ≤ 2500 M\le 2500M≤2500。对于70 % 70\%70%的数据N ≤ 500 N\le 500N≤500M ≤ 10 4 M\le 10^4M≤104。对于100 % 100\%100%的数据1 ≤ N ≤ 5000 1\le N\le 50001≤N≤50001 ≤ M ≤ 2 × 10 5 1\le M\le 2\times 10^51≤M≤2×1051 ≤ Z i ≤ 10 4 1\le Z_i \le 10^41≤Zi​≤1041 ≤ X i , Y i ≤ N 1\le X_i,Y_i\le N1≤Xi​,Yi​≤N。样例解释所以最小生成树的总边权为2 2 3 7 22372237。2.主要思路这道题是最小生成树的模板题所以我们可以用Kruskal 算法并查集解决。首先我们需要明确题目的要求找无向图中连接所有节点、总权值最小的边集不连通就输出orz。Kruskal 算法的核心就是贪心先把所有边按权值从小到大排序再依次选则边用并查集判断两点是否连通不连通就选这条边合并集合。我的代码实现主要分为三步一是初始化并查集每个节点自己是父节点二是排序所有边保证从短边开始选三是遍历边用find找根节点不同根就合并累加权值统计选边数。最后判断选够n-1条边就是连通的那么就输出总权值否则输出orz。3.AC代码#includebits/stdc.husingnamespacestd;intn,m,fa[200005],s0,sum0;structshu{intx,y,z;}a[200005];boolcmp(shu c,shu v){returnc.zv.z;}intfind(intx){if(fa[x]x)returnx;elsereturnfa[x]find(fa[x]);}intmain(){cinnm;for(inti1;in;i)fa[i]i;for(inti1;im;i){cina[i].xa[i].ya[i].z;}sort(a1,am1,cmp);for(inti1;im;i){intx1find(a[i].x);inty1find(a[i].y);if(x1!y1){fa[x1]y1;s1;suma[i].z;}if(sn-1)break;}if(sn-1)coutorz;elsecoutsum;return0;}以上就是本篇全部内容感谢浏览