poj1251--Kruskal

古城微笑少年丶 2022-04-10 09:55 180阅读 0赞

/*
    * poj1251-- Kruskal
    * date 2014/7/15
    * state AC
    */
    
    #include <iostream>
    #include <algorithm>
    #include <fstream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int const MAXN=30+100;
    int u[MAXN];
    int v[MAXN];
    int w[MAXN+50];
    
    int p[MAXN];
    int r[MAXN];
    
    int cmp(const int i,const int j)
    {
        return w[i]<w[j];
    }
    
    int unionFindSet(int x)
    {
        return p[x]==x?x:p[x]=unionFindSet(p[x]);
    }
    
    int Kruskal(int n,int m)
    {
        int ans=0;
    
        //memset(p,0,sizeof(p));
        //memset(r,0,sizeof(r));
    
        for(int i=0;i<n;i++)
            p[i]=i;
        for(int i=0;i<m;i++)
            r[i]=i;
    
        //mem
        sort(r,r+m,cmp);
        for(int i=0;i<m;i++)
        {
            int e=r[i];
            int x=unionFindSet(u[e]);
            int y=unionFindSet(v[e]);
            if(x!=y)
            {
                ans+=w[e];
                p[x]=y;
            }
        }
        return ans;
    }
    int main()
    {
        //cout << "Hello world!" << endl;
        //freopen("input.txt","r",stdin);
        char a[2],b[2];
        int c;
        int m;
        int n;
        int edgeNum;
        while(scanf("%d",&n))
        {
            if(n==0)break;
    
            memset(u,0,sizeof(u));
            memset(v,0,sizeof(v));
            memset(w,0,sizeof(w));
    
            edgeNum=0;
            for(int i=0;i<n-1;i++)
            {
                scanf("%s%d",a,&m);
                for(int j=0;j<m;j++)
                {
                    scanf("%s%d",b,&c);
                    u[edgeNum]=a[0]-'A';
                    v[edgeNum]=b[0]-'A';
                    w[edgeNum]=c;
                    edgeNum++;
                }
            }
            //
            /*cout<<"edgeNumber: "<<edgeNum<<endl;
            for(int k=0;k<edgeNum;k++)
                cout<<u[k]<<" "<<v[k]<<" "<<w[k]<<"    ";
            cout<<"---"<<endl;
            */
            cout<<Kruskal(n,edgeNum)<<endl;
        }
        return 0;
    }