H题解--“歌尔创客杯”第二届哈尔滨理工大学（荣成）程序设计竞赛

H 修建道路
最小生成树，模板题。
所有城市两两可达，最少边数为n-1，然后再保留一下加入边的最大权值就行。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct node{
    int u,v,c;
}a[N];
int n,m,ans,fa[N];
bool cmp(node x,node y){return x.c<y.c;}//所有边按权值大到小排序
int find(int x){//并查集查找
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);
    sort(a+1,a+m+1,cmp);    
    for(int i=1,k=0;i<=m;i++){
        int fx=find(a[i].u),fy=find(a[i].v);
        if(fx!=fy){
            fa[fy]=fx;//并查集合并
            ans=max(ans,a[i].c);//更新最大权值
            if(++k==n-1) break;
        }
    }    
    printf("%d %d\n",n-1,ans);
    return 0;
}