POJ1251_Jungle Roads ——最小生成树

题目链接：http://poj.org/problem?id=1251

题意：求最小生成树

输入N

接下来N-1行表示点的连接关系

每行输入  起点字母    n（和它连接的点的数目）   终点  权值。。。

当N=0时，程序结束

做法：Kruskal算法

Kruskal算法：处理元素是 边   ，边的信息是：起点、终点、权值

按照边的权值从小到大排序   每次添加一条边时 检测起点、终点是否属于同一个“祖先” *

不是则添加，是则不添加。

#include<cstdio>
#include<algorithm>
const int N=666;
int parent[N];
struct Edge
{
    int s,e,dis;
    bool operator<(const Edge &b)const{
    return dis<b.dis;
    }
}edge[N];
int find(int x){
    return x==parent[x]?x:find(parent[x]);
}
int kruskal(int n)
{
    int ans=0;
    for(int i=0;i<N;++i)parent[i]=i;
    std::sort(edge,edge+n);
    for(int i=0;i<n;++i){
        int x=find(edge[i].s);
        int y=find(edge[i].e);
        if(x!=y){
            ans+=edge[i].dis;
            parent[y]=x;
        }
    }
    return ans;
}
int  main()
{
    int n,m,k,dis;
    char str[2],t_str[2];
    while(scanf("%d",&n),n){
        k=0;
        for(int i=0;i<n-1;++i){
                scanf("%s %d",str,&m);
                for(int j=0;j<m;++j){
                    scanf("%s %d",t_str,&dis);
                    edge[k].s=str[0]-'A';
                    edge[k].e=t_str[0]-'A';
                    edge[k].dis=dis;
                    edge[++k].e=str[0]-'A';
                    edge[k].s=t_str[0]-'A';
                    edge[k].dis=dis;
                }
        }
        printf("%d\n",kruskal(k));
    }
}