POJ 1861 ——Network——————【最小瓶颈生成树】

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn = 1010;
const int maxe = 15010;
struct Edge{
    int from,to,dist,idx;
    Edge(){}
    Edge(int _from,int _to,int _dist,int _idx):from(_from),to(_to),dist(_dist),idx(_idx){}
}edges[maxe];
struct Set{
    int pa,rela;
}sets[maxn];
int ans[maxn];
bool cmp(Edge a,Edge b){
    return a.dist < b.dist;
}
void init(int n){
    for(int i = 0; i <= n; i++){
        sets[i].pa =  i;
    }
}
int Find(int x){
    if(x == sets[x].pa){
        return x;
    }
    int tmp = sets[x].pa;
    sets[x].pa = Find(tmp);
    return sets[x].pa;
}
int main(){
    int n, m;
    while(scanf("%d%d",&n,&m)!=EOF){
        init(n);
        int a,b,c;
        for(int i = 0; i < m; i++){
            scanf("%d%d%d",&a,&b,&c);
            edges[i] = Edge(a,b,c,i);
        }
        sort(edges,edges+m,cmp);
        int cnt = 0;
        for(int i = 0; i < m; i++){
            Edge & e = edges[i];
            int rootx, rooty;
            rootx = Find(e.from);
            rooty = Find(e.to);
            if(rootx == rooty){
                continue;
            }
            sets[rooty].pa = rootx;
            ans[cnt++] = i;
        }
        printf("%d\n",edges[ans[cnt-1]].dist);
        printf("%d\n",cnt);
        for(int i = 0; i < cnt; i++){
            printf("%d %d\n",edges[ans[i]].from,edges[ans[i]].to);
        }
    }
    return 0;
}