poj 1861 Network MST

    期末后第一次写题，结果就是这么灵异的一题……

    样例是错的，这题实际上就是求个最小生成树，spj

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
struct edge
{
    int f,t,v;
};
bool cmp(edge a,edge b)
{
    return a.v<b.v;
}
edge e[15005];
int fa[1005];
int far(int nn)
{
    if(fa[nn]<0)return nn;
    return fa[nn]=far(fa[nn]);
}
int main()
{
    memset(fa,-1,sizeof(fa));
    int n,m,f,t,v;
    scanf("%d%d",&n,&m);
    int i;
    for(i=0;i<m;i++)
        scanf("%d%d%d",&e[i].f,&e[i].t,&e[i].v);
    sort(e,e+m,cmp);
    int now,k,Max;
    int ans[1000];
    for(k=Max=0,now=1;now<n;k++)
    {
        f=far(e[k].f);t=far(e[k].t);
        if(f==t)continue;
        Max=max(Max,e[k].v);
        if(fa[f]<fa[t])//加权法则，避免退化
        {
            fa[f]+=fa[t];
            fa[t]=f;
        }
        else
        {
            fa[t]+=fa[f];
            fa[f]=t;
        }
        ans[now]=k;
        now++;
    }
    printf("%d\n",Max);
    printf("%d\n",now-1);
    for(i=1;i<now;i++)
     printf("%d %d\n",e[ans[i]].f,e[ans[i]].t);

}