Posted on 2011-11-05 19:44
C小加 閱讀(1353)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
題意：
在相通n個(gè)島嶼的所有橋都?jí)牧耍匦蓿匦廾恳粋€(gè)橋所用的時(shí)間不同，求重修使每個(gè)島嶼都間接或直接與其他島嶼相同時(shí)所用的的最短時(shí)間（只有修完一個(gè)橋后才可修下一個(gè)橋）。
思路：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;
}