Posted on 2011-11-05 19:44
C小加 阅读(1338)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
题意：
在相通n个岛屿的所有桥都坏了，要重修，重修每一个桥所用的时间不同，求重修使每个岛屿都间接或直接与其他岛屿相同时所用的的最短时间（只有修完一个桥后才可修下一个桥）。
思路：10月份月赛唯一过的题。裸体的最小生成树，我用的是Kruskal+并查集。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX=27*27+1;
typedef struct
{
int a,b;
int len;
}node;
node nod[MAX];
int father[MAX];
int cmp(node b1,node b2)
{
return b1.len<b2.len;
}
int find(int x)
{
return father[x]==x?x:father[x]=find(father[x]);
}
void Union(int a1,int a2)
{
father[a1]=a2;
}
int main()
{
int n;
while(cin>>n&&n)
{
memset(nod,0,sizeof(nod));
int i;
for(i=0;i<=MAX;i++)
{
father[i]=i;
}
int tempn=n,cnt=0;
tempn--;
while(tempn--)
{
string s1;
cin>>s1;
int qn;
cin>>qn;
if(qn==0) continue;
while(qn--)
{
string s2;
cin>>s2;
int len;
cin>>len;
nod[cnt].a=s1[0]-'A'+1;
nod[cnt].b=s2[0]-'A'+1;
nod[cnt].len=len;
cnt++;
}
}
sort(nod,nod+cnt,cmp);
int sum=0;
for(i=0;i<cnt;i++)
{
int x=find(nod[i].a);
int y=find(nod[i].b);
if(x==y)
continue;
else
{
Union(x,y);
sum+=nod[i].len;
}
}
cout<<sum<<endl;
}
return 0;
}