HDU 1301 Jungle Roads

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

最简单的最小生成树

#include <stdio.h>
#include <stdlib.h> 
int p[30];
int cnt,n; 
typedef struct L
{
    int a,b,d;
}L;
L r[1000];     
int cmp(const void*a,const void*b){return (*(struct L*)a).d-(*(struct L*)b).d;} 
int find(int x){return p[x]==x?x:p[x]=find(p[x]);} 
int Kruskal()
{
    int i,ans=0;
    int x,y; 
    for(i=0;i<n;i++)p[i]=i; 
    qsort(r,cnt,sizeof(L),cmp);
    for(i=0;i<cnt;i++)
    {
        x=find(r[i].a);
        y=find(r[i].b);
        if(x!=y){ans+=r[i].d;p[x]=y;} 
    }
    return ans; 
}
int main()
{
    int m,i,j;
    int dis; 
    char rt,lf; 
    while(scanf("%d%*c",&n),n)
    {
        cnt=0; 
        for(i=0;i<n-1;i++)
        { 
            scanf("%c%d%*c",&rt,&m); 
            for(j=0;j<m;j++)
            { 
                scanf("%c%d%*c",&lf,&dis); 
                r[cnt].a=rt-'A';
                r[cnt].b=lf-'A';
                r[cnt++].d=dis; 
            }
        }
        printf("%d\n",Kruskal()); 
    }
    return 0;
}