P1111 修复公路（并查集）
zhouwc
2018-02-23 15:05:34
这道题我最大的失误是，排序的时候把m排成了n，导致WA。
这道题还是很有价值的，仔细去看看。
还有有一篇题解写的挺不错的
```cpp
#include<bits/stdc++.h>
using namespace std;
int num[1005],f[1005],n,m;
struct zwc
{
int x,y,z;
}l[100005];
bool cmp(struct zwc a,struct zwc b)
{
return a.z<b.z;
}
int findfa(int x)
{
if (f[x]!=x) f[x]=findfa(f[x]);
return f[x];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&l[i].x,&l[i].y,&l[i].z);
}
sort(l+1,l+m+1,cmp);
for (int i=1;i<=n;i++)
{
f[i]=i;
num[i]=1;
}
for (int i=1;i<=m;i++)
{
int a=findfa(l[i].x);
int b=findfa(l[i].y);
if (a!=b)
{
if(num[a]>num[b])
{
f[b]=a;
num[a]+=num[b];
}
else
{
f[a]=b;
num[b]+=num[a];
}
}
if (num[findfa(l[i].x)]>=n)
{
printf("%d",l[i].z);
return 0;
}
}
printf("-1");
return 0;
}
```