讨论 / 最小生成树
席一鸣 2014-10-04 01:48:43
点我顶贴 收藏 删除
#include<algorithm>

#include<iostream>

using namespace std;

struct q

{

int a,b,c;

}p[100001];

int f[100001];

int c(q a,q b)

{

return a.c<b.c;

}

int find(int x)

{

if(f[x]!=x)

f[x]=find(f[x]);

return f[x];

}

main()

{

int m,n,i,x,y,k=0;

long long s=0,t=0;

cin>>n>>m;

for(i=1;i<=n;i++)

f[i]=i;

for(i=1;i<=m;i++)

{

cin>>p[i].a>>p[i].b>>p[i].c;

t+=p[i].c;

}

sort(p+1,p+m+1,c);

for(i=1;i<=m;i++)

{

x=find(p[i].a);

y=find(p[i].b);

if(x!=y)

{

f[x]=y;

s+=p[i].c;

k++;

if(k==n-1)

break;

}

}

cout<<t-s;

}

查看更多回复
提交回复