题意:每几个村庄都有连通的路,而每条路都有维修费,叫你找出能联通所有村庄的路的最小维修费.
思路:最小生成树的水题,把每一条路的维修费看成连接两个村庄的路的长度,即找出连接所有村庄的路的总和最小是多少.可以用krusual或prime算法做,我推荐用kruskal做,因为krusual思想比较简单易懂,实行起来也比较方便.
需要注意的是在主函数中存入输入数据的问题,因为有字符,则会车和空格都要影响.所以需要特别注意下输入格式.(%s就很好哦).
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxp=1000;
int father[maxp];
int cnt;
struct edge
{
int u,v,w;
}s[maxp];
int p,l;
int Find(int x)
{
if(father[x]<0) return x;
return Find(father[x]);
}
void Union(int x,int y)
{ int m=Find(x);
int n=Find(y);
int tmp=father[m]+father[n];
if(father[m]>father[n]){
father[m]=n;
father[n]=tmp;
}
else{
father[n]=m;
father[m]=tmp;
}
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
void kruskal()
{ int u,v;
int rode=0;
int sum=0;
memset(father,-1,sizeof(father));
for(int i=0;i<l;i++){
u=s[i].u,v=s[i].v;
if(Find(u)!=Find(v))
{
rode+=s[i].w;
sum++;
Union(u,v);
}
if(sum>=p-1);
}
printf("%d\n",rode);
}
int main()
{
while(~scanf("%d",&p)&&p)
{
char c;
int t;
memset(s,0,sizeof(s));
l = 0;
getchar();
for(int i=1;i<p;i++)
{
cin>>c;
scanf("%d",&t);
getchar();
while(t--)
{
char c2;
int x;
scanf("%c",&c2);
scanf("%d",&x);
getchar();
s[l].u=c-'A'+1;
s[l].v=c2-'A'+1;
s[l].w=x;
//printf("%d %d %d\n",u,v,w);
l++;
}
//printf("%d %d\n",u,i);
}
sort(s,s+l,cmp);
kruskal();
}
}
