HDU 1233 还是畅通工程

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

最小生成树,查找根节点的函数里面等号写成赋值号,查了半个小时、、、

View Code
#include <stdio.h>
#include <stdlib.h>
#define N 110
int idx[N];
struct node{
    int a,b,d;
}r[N*(N-1)/2];
int cmp(const void*a,const void*b)
{
    return (*(struct node*)a).d-(*(struct node*)b).d;
}
int find(int n)
{
    return idx[n]==n?n:idx[n]=find(idx[n]);
}
int main()
{
    int i,n,m;
    int p,q;
    while(~scanf("%d",&n),n)
    {
        for(i=1;i<=n;i++)
            idx[i]=i;
        m=n*(n-1)/2;
        for(i=0;i<m;i++)
            scanf("%d%d%d",&r[i].a,&r[i].b,&r[i].d);
        qsort(r,m,sizeof(struct node),cmp);
        int cnt=0;
        int d=0;
        for(i=0;cnt<n-1;i++)
        {
            p=find(r[i].a);
            q=find(r[i].b);
            if(p!=q)
            {
                d+=r[i].d;
                idx[p]=q;
                cnt++;
            }
        }
        printf("%d\n",d);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/xiaohongmao/p/2445195.html