#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=1e5+10; int n,m; struct node{ int a,b,w; bool operator< (const node& W)const //每条边按权重排序 { return w<W.w; } }nod[N]; int p[N]; int find(int x) //并查集模版 { if(p[x]==x) return x; p[x]=find(p[x]); return p[x]; } int main(void) { cin>>n>>m; for(int i=0;i<m;i++) { int a,b,w; cin>>a>>b>>w; nod[i]={a,b,w}; } sort(nod,nod+m); for(int i=1;i<=n;i++) p[i]=i; int res=0,cnt=0; for(int i=0;i<m;i++) { int a=nod[i].a; int b=nod[i].b; int w=nod[i].w; a=find(a),b=find(b); if(a!=b) //如果a集合和b集合没连上,就连上,边数++; { res+=w; cnt++; p[a]=b; } } if(cnt<n-1) //n个点至少需要n-1个边 ,小于就是无法构成最短生成树 puts("impossible"); else cout<<res<<endl; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:546 |
C语言训练-立方和不等式 (C语言代码)浏览:774 |
人见人爱A+B (C语言代码)浏览:655 |
C语言训练-阶乘和数* (C语言代码)-------- 呆板写法浏览:1389 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:532 |
字符逆序 (C语言代码)浏览:496 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:1264 |
多输入输出练习2 (C语言代码)浏览:1691 |
买不到的数目 (C语言代码)浏览:3116 |
简单的a+b (C语言代码)浏览:485 |