poj 1861 Network 最小生成树 kruscal算法

链接：http://poj.org/problem?id=1861

题意：给n个路由器，注意标号为1到n，m表示这n个路由器之间的连接关系数，要连接这些路由器，且必须保证最长的单根网线的长度是所有方案中最小的。输出连接方案中最长网线的长度和所用网线的根数以及每根网线所连路由器的编号。

思路：没有直接要求求最小生成树，可以知道，所选网线条数必是n-1。另外，可以证明，对于一个图的最小生成树来说，它的最大边满足在所有生成树的最大边里最小。由于kruscal算法是先选长度较小的边，所以长度最大的边必然是最后选定的一条边。

还有，poj和zoj上的这道题Sample Output有错误。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;

const int maxn=1000+5;
const int maxm=15000+5;
int n,m,maxedge;
int flag[maxn];//保存所选边的下标

struct Edge
{
    int u,v,w;
}edges[maxm];
class set
{
public:
    void makeset(int n)
    {
        for(int i=1; i<=n; i++)
        {
            father[i]=i;
            rank[i]=1;
        }
    }
    int findset(int x)
    {
        if(x!=father[x])
            father[x]=findset(father[x]);
        return father[x];
    }
    void unionset(int x,int y)
    {
        x=findset(x);
        y=findset(y);
        if(x==y)  return;
        if(rank[x]>rank[y])
        {
            father[y]=x;
            rank[x]+=rank[y];
        }
        else
        {
            father[x]=y;
            rank[y]+=rank[x];
        }
    }
private:
    int father[maxn];
    int rank[maxn];
} ufs;
int cmp(const void* a,const void* b)
{
    Edge aa=*(const Edge*)a, bb=*(const Edge*)b;
    return aa.w-bb.w;
}
void kruscal()
{
    int u,v,num=0,k=0;
    ufs.makeset(n);//泪。。。
    for(int i=0;i<m;i++)
    {
        u=edges[i].u;v=edges[i].v;
        if(ufs.findset(u)!=ufs.findset(v))
        {
            num++;
            ufs.unionset(u,v);
            maxedge=edges[i].w;
            flag[k++]=i;
        }
        if(num>=n-1) break;
    }
}

int  main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<m;i++)
            scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);
        qsort(edges,m,sizeof(edges[0]),cmp);
        kruscal();
        printf("%d\n",maxedge);
        printf("%d\n",n-1);
        for(int i=0;i<n-1;i++)
            printf("%d %d\n",edges[flag[i]].u,edges[flag[i]].v);
    }
    return 0;
}

一开始写的时候忘记给并查集初始化了，嗯，后面才检查出来。写代码时要全神贯注啊。失之毫厘，谬以千里。