Posted on 2011-11-05 19:44
C小加 閱讀(1353)
評論(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;
}