pku1251 Jungle Roads(最小生成树)

题目:

题目大意就不用说了，一看图就知道了。典型的最小生成树，直接套Prim模板就可以。Prim的大致为贪心思想，每次选择是小权值边进行贪心。与Dij异曲同工，一个前者每次选择最小边，后者每次选择最短距离的顶点。这题直接敲Prim，一次AC。郁闷的是，这题我敲Kruscal,WA..

my code:

 

#include<iostream>
using namespace std;

const int inf=0x7fffffff;
const int maxint=50;

int Prim(int n,int c[50][50])
{
    int lowcost[maxint];
    int close[maxint];
    int mit,i,j,k,MIN;bool s[maxint];
    for(i=1;i<=n;i++)
    {
        lowcost[i]=c[1][i];
        close[i]=1;
        s[i]=0;
    }
    s[1]=1;mit=0;
    for(i=1;i<n;i++)
    {
        MIN=inf;
        for(j=2;j<=n;j++)
        {
            if(!s[j]&&MIN>lowcost[j])
            {
                MIN=lowcost[j];
                k=j;
            }
        }
        mit+=lowcost[k];s[k]=1;
        for(j=2;j<=n;j++)
        {
            if(!s[j]&&lowcost[j]>c[j][k])
            {
                lowcost[j]=c[j][k];
                close[j]=k;
            }
        }
    }
    return mit;
}
int main()
{
    int n,i,j,t,dis;
    int c[50][50];
    char a,b;
    while(cin>>n&&n)
    {
        for(i=1;i<=n;i++)for(j=1;j<=n;j++) c[i][j]=inf;
        for(i=1;i<n;i++)
        {
            cin>>a>>t;
            for(j=1;j<=t;j++)
            {
                cin>>b>>dis;
                if(c[a-'A'+1][b-'A'+1]>dis)
                {
                    c[b-'A'+1][a-'A'+1]=dis;
                    c[a-'A'+1][b-'A'+1]=dis;
                }
            }
        }
        cout<<Prim(n,c)<<endl;
    }
    return 0;
}