37
解题思路:用克鲁斯卡尔算法就行(很久没写了,有点生-,-)
代码如下:
#include <cstdio> #include <algorithm> using namespace std; int fa[1010]; struct node { int u,v,power; }bian[50010]; bool cmp(struct node a,struct node b) { return a.power<b.power; } int find(int x) { int r=x; while(r!=fa[r]) { r=fa[r]; } return r; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { fa[i]=i; } for(int i=0;i<m;i++) { int s,e,w; scanf("%d%d%d",&s,&e,&w); bian[i].u=s; bian[i].v=e; bian[i].power=w; } sort(bian,bian+m,cmp); int sum=0; for(int i=0;i<m;i++) { int s,e,w; s=bian[i].u; e=bian[i].v; w=bian[i].power; int fx=find(s),fy=find(e); if(fx!=fy) { fa[fx]=fy;//很久没写这里刚开始写成了fa[s]=e;。。。这样写错的话原来的s就与之前的集合断了联系,画个图就明白了 sum=sum+w; } } printf("%d\n",sum); return 0; }