【c++ 图论例题学习】洛谷 P3366 最小生成树
题目描述如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。
输入格式第一行包含两个整数 N,MN,M,表示该图共有 NN 个结点和 MM 条无向边。
接下来 MM 行每行包含三个整数 X_i,Y_i,Z_iXi,Yi,Zi,表示有一条长度为 Z_iZi 的无向边连接结点 X_i,Y_iXi,Yi。
输出格式如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例输入 #1 复制
4 51 2 21 3 21 4 32 3 43 4 3 输出 #1 复制
7 说明/提示数据规模:
对于 20%20% 的数据,N\le 5N≤5,M\le 20M≤20。
对于 40%40% 的数据,N\le 50N≤50,M\le 2500M≤2500。
对于 70%70% 的数据,N\le 500N≤500,M\le 10^4M≤104。
对于 100%100% 的数据: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。
样例解释:
所以最小生成树的总边权为 2+2+3=72+2+3=7。
具体做法:(如有问题可以私信,还请各位多多包含)
#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;struct node{int u,v,w,next;
//结构体储存 u(起点),v(终点),w(当前路径的权值),next(当前路径的上一条边)}e[1010101];int m,n;int f[1010101];//定义数组,为了“找爹”(往下看);int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);//递归函数,找到两个点共同的"爹"(假设点 a 连接点 b,点 a 也连接点 c,那么点 c 和点 b 虽然不直接连接,但是两个点的“爹”也就是 a 是同一个爹,所以两个点依旧相连)}inline int kruskal(){int val=0,cnt=0;//vla 记录最小路径,cnt 记录当前边数 sort(e+1,e+1+m);//排序 for(int i=1;i<=m;i++){//定义了 ecnt,建议使用 ecnt(不理解的见下文)int u=e[i].u,v=e[i].v;//找“爹”int xx=getf(u);int yy=getf(v);if(xx!=yy){//如果两人爹不同,那么就加边,同时记录路径的值;cnt++,val+=e[i].w,f[xx]=yy;//因为已经将两个点相连,所以同步两个点的“爹”(注:f[yy]=xx 意思相同)}if(cnt==n-1) return val;//因为 n 个点,所以有 n-1 条边,当 cnt 等于 n-1 时,就可以跳出}return -1;}int main(){cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].w;/*这里建议单独开一个函数;将输入改成 int a,b,c;cin>>a>>b>>c;addedge(a,b,c);在上方写一个函数(此题暂时不需要 e[].next)开始加边;int ecnt=0;记录边数 void addedge(int u,int v,int w){e[++ecnt].u=u;e[ecnt].v=v;e[ecnt].w=w;}*/}int x=kruskal();if(x==-1)cout<<"orz";elsecout<<x;return 0;}
考虑到这是一道模板题,所以梳理思路很重要
版权声明: 本文为 InfoQ 作者【贤鱼很忙】的原创文章。
原文链接:【http://xie.infoq.cn/article/383f35c66b9017392fa9a5689】。未经作者许可,禁止转载。
评论