题目链接：

PKU:http://poj.org/problem?id=1861

ZJU:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=542

Description

Input

Output

Sample Input

4 6

1 2 1

1 3 1

1 4 2

2 3 1

3 4 1

2 4 1

Sample Output

1

4

1 2

1 3

2 3

3 4

Source

题意：

有n个顶点，m条边，每条边都是双向的，而且有一定的长度。要求使每一个顶点都连通，而且要使总长度最短，

输出最大边、边的总数和所选择的边。

PS:

貌似题目的案例有点问题，卡了好久！

应该输出的是：

1

3

1 3

2 3

2 4

代码例如以下：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 15017;

int father[maxn];

struct edge

{

    int x,y,v;

};

struct edge ed[maxn],ansa[maxn];

bool cmp(edge a,edge b)

{

    return a.v<b.v;

}

int find(int x)

{

    if(x==father[x])

        return x;

    return father[x]=find(father[x]);

}

void Krusal(int n,int m)

{

    int i,fx,fy,cnt;

    int ans=0;

    for(i = 1; i <= n; i++)

        father[i]=i;

    sort(ed,ed+m,cmp);//对边的排序

    cnt=0;

    int max=-1;

    for(i=0; i<m; i++)

    {

        fx=find(ed[i].x);

        fy=find(ed[i].y);

        if(fx!=fy)

        {

            ans+=ed[i].v;

            father[fx]=fy;

            ansa[cnt].x=ed[i].x;

            ansa[cnt++].y=ed[i].y;

            if(max<ed[i].v)

                max=ed[i].v;

        }

    }

    printf("%d\n%d\n",max,cnt);

    for(i=0; i<cnt; i++)

        printf("%d %d\n",ansa[i].x,ansa[i].y);

}

int main()

{

    int t;

    int n, m;

    int a, b, k;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        for(int i = 0; i < m; i++)

        {

            scanf("%d %d %d",&a,&b,&k);

            ed[i].x=a,ed[i].y=b,ed[i].v=k;

        }

        Krusal(n,m);

    }

    return 0;

}