POJ – 1251 Jungle Roads

嘿嘿嘿,从今天开始写博客啦!
接下来应该会每天更新,顺便复习一些算法再补补题。

咳咳咳,进入正题,这题是一道典型的最小生成树问题,题意大概就是讲有n个点,然后n-1个行描述关系,每行第一个数字表示有多少条线与前面的点相连,后面的数字则为边权值。

这题可以采用prim算法或者是kruskal算法来解决,算是模板题啦。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int par[200005];
int rak[200005];
int cnt;

struct edge
{
    int u,v,cost;//u,v表示点,cost表示权值
};
edge es[155];
//并查集初始化
void init(int n)
{
    for(int i=0;i<=n;i++)
    {
        par[i]=i;
        rak[i]=0;
    }
}
int find(int x)
{
    if(par[x]==x)
        return x;
    else
        return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)
        return ;
    if(rak[x]<rak[y])
    {
        par[x]=y;
    }
    else
    {
        par[y]=x;
    }
    if(rak[x]==rak[y])
        rak[x]++;
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
bool cmp(const edge&e1,const edge&e2)
{
    return e1.cost<e2.cost;
}

int kruskal()
{
    sort(es,es+cnt,cmp);
    //cout<<cnt;
    init(155);
    int res=0;
    for(int i=0;i<cnt;i++)
    {
        edge e=es[i];
        //printf("%d %d\n",e.u,e.v);
        if(!same(e.u,e.v))
        {
            unite(e.v,e.u);
            res+=e.cost;
            //printf("%d\n",res);
        }
    }
    return res;
}
int main()
{
    char c[10];
    int n;
    int num;
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        //init(105);
        if(n<=0)
            break;
        for(int i=0;i<n-1;i++)
        {
            scanf("%s %d",c,&num);
            int u=c[0]-'A';
            for(int j=0;j<num;j++)
            {
                int b;
                scanf("%s %d",c,&b);
                int v=c[0]-'A';
                es[cnt].u=u;
                es[cnt].v=v;
                es[cnt++].cost=b;
                //printf("%d %d %d\n",u,v,b);
                //kruskal(n);
                //printf("%d\n",kruskal(n));
            }
        }
        printf("%d\n",kruskal());
    }
}

补这道题的时候本以为很快就能AC,可是第一组测试数据一直是0, 
调试了大概半个小时才发现原来我在并查集的初始化里将cnt也初始化了,导致了kruskal根本就没有运算,呜呜呜,下次一定要注意了。