最小生成树
陈子骏
2018-04-02 17:45:57
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
int sum[10001],f[10001],tt,s;
struct note
{
int start,end,time;
}shu[200001];
int cmp(const note &a,const note &b)
{
if(a.time<b.time) return 1;
return 0;
}
int get(int v)
{
if(f[v]==v) return v;
else
{
f[v]=get(f[v]);
return f[v];
}
}
void merge(int t1,int t2)
{
int fu1,fu2;
fu1=get(t1); fu2=get(t2);
if(fu1!=fu2)
{
f[fu2]=fu1;
sum[fu1]=sum[fu2]+sum[fu1];
tt=tt+s;
}
return;
}
using namespace std;
int main()
{
int i,flag=0;
int n,m;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) {f[i]=i; sum[i]=1;}
for(i=1;i<=m;i++)
{
cin>>shu[i].start>>shu[i].end>>shu[i].time;
}
sort(shu+1,shu+m+1,cmp);
for(i=1;i<=m;i++)
{
s=shu[i].time;
merge(shu[i].start,shu[i].end);
if(sum[get(shu[i].start)]==n)
{
flag=1;
break;
}
}
if(flag==1) cout<<tt;
else cout<<"orz";
}
```