POJ--1251题解 最小生成树模板题

题意:每几个村庄都有连通的路,而每条路都有维修费,叫你找出能联通所有村庄的路的最小维修费.

思路:最小生成树的水题,把每一条路的维修费看成连接两个村庄的路的长度,即找出连接所有村庄的路的总和最小是多少.可以用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();
    }
}