百炼 1251:丛林中的路（Kruskal）

描述

 

热带岛屿Lagrishan的首领现在面临一个问题：几年前，一批外援资金被用于维护村落之间的道路，但日益繁茂的丛林无情的侵蚀着村民的道路，导致道路维修开销巨大，长老会不得不放弃部分道路的维护。上图左侧图显示的是正在使用道路的简图以及每条路每个月的维修费用（单位为aacms）。现在长老会需要提出一种方案，即需要保证村落之间都可以互相到达，又要将每个月的道路维修费用控制在最小。村子编号为从A到I。上图右侧显示的方案最小维修开销为216 aacms每月。

输入输入包含1~100个数据集，最后一行为0.每个数据集第一行为村落数目n, 1 < n < 27,依次用字母表的前n个字母标记。接下来有n-1行，每行的第一个数据便是按字母顺序排列的村子编号（不包括最后一个村庄）。每个村庄后面的数据k代表该村庄通往编号在其之后的村庄的道路数目，如A 2 B 12 I 25，代表A村庄有2个编号在A之后的村庄和其相连。若k大于0，k后面会依次给出这k个村庄的编号以及各自到起始村庄的道路维修费用，如A 2 B 12 I 25，代表A和B之间道路维修费用为12， A和I之间道路维修费用为25（维修费用为不超过100的正整数）.路的总数目不超过75条，每个村庄到其他村庄不会有超过15条路（包括编号在其之前和之后的）。输出每个数据集有一个输出：针对解决方案每个月维修道路的小费用。
提示：蛮力算法虽能找出解决方案，但将会超出时间限制。样例输入

 

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

样例输出

216
30

 

Kruskal算法模板题

#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

int n;
int cnt=0;
char fa[200];
int sum=0;

struct node
{
    char x,y;
    int dis;
}edg[200];


bool cmp(node a,node b)
{
    return a.dis<b.dis;
}

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        char temp=i+'A';
        fa[temp]=temp;
    }
}

char _find(char x)
{
    if(fa[x]==x)
    {
        return x;
    }
    else
        return fa[x]=_find(fa[x]);
}

void _union(char x,char y)
{
    char tempx=_find(x);
    char tempy=_find(y);
    if(tempx!=tempy)
    {
        fa[tempx]=tempy;
    }

}

int main()
{

    while(cin>>n&&n!=0)
    {
        cnt=0;
        init(n);

        for(int i=0;i<n-1;i++)
        {
            char c1,c2;
            int num,d;
           cin>>c1>>num;
            for(int j=0;j<num;j++)
            {
                cin>>c2>>d;
                edg[cnt].x=c1;
                edg[cnt].y=c2;
                edg[cnt++].dis=d;
            }
        }


        sort(edg,edg+cnt,cmp);

        sum=0;
        int a=0;

        for(int i=0;i<cnt;i++)
        {
            char tempx=edg[i].x;
            char tempy=edg[i].y;
            if(_find(tempx)!=_find(tempy))
            {
                _union(tempx,tempy);
                sum+=edg[i].dis;
                a++;

            }
        }

        if(a==n-1)
        {
           cout<<sum<<endl;
        }
    }

    return 0;
}