学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1863

题意：求最小生成树。

思路：克鲁斯卡尔算法。

代码是自己根据对克鲁斯卡尔的理解写的，可能不够精简，所以仅供参考，不足为训，还望高人指点。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct ln
{
    int a,b,c;
}con[10000];

int set[1000];

int cmp(const void *p,const void *q)
{
    return (*(struct ln*)p).c>=(*(struct ln*)q).c?1:-1;
}

int find(int x)
{
    while(set[x]!=x)
        x=set[x];
    return x;
}

void merge(int x,int y) 
{
    x=find(x);
    y=find(y);
    if(y<x)
        set[x]=y;
    else if(y>x)
        set[y]=x;
}

main()
{
    int n,m,i,t,use[1000],cost,cnt;
    while(scanf("%d %d",&n,&m)&&n)
    {
        for(i=1;i<=m;i++)
        {
            set[i]=i;
        }
        memset(use,0,sizeof(use));
        for(i=0;i<n;i++)
        {
            scanf("%d %d %d",&con[i].a,&con[i].b,&con[i].c);
        }
        qsort(con,n,sizeof(struct ln),cmp);
        cost=0;
        t=m;
        for(i=0;i<n&&i<t-1;i++)
        {
            if(!use[con[i].a])
                use[con[i].a]=1;
            if(!use[con[i].b])
                use[con[i].b]=1;
            if(find(con[i].a)==find(con[i].b))//在同一连通分量
                t++;
            else
            {
                merge(con[i].a,con[i].b);
                cost+=con[i].c;
            }
        }
        for(cnt=0,i=1;i<=m;i++)
        {
            if(i==set[i])
                cnt++;
        }
        if(cnt==1)
            printf("%d\n",cost);
        else
            printf("?\n");
    }
    return 0;
}