hdu 1301

最小生成树模板题
简单的prim算法
AC代码：
#include <iostream>

#include <stdio.h>

#define INF 9999999

using namespace std;

int map[200][200],dis[200],vis[200];

int prim(int n)

{

    int i,j,min,p;

    for(i=1;i<=n;i++)

    {

        dis[i]=map[1][i];

        vis[i]=0;

    }

    vis[1]=1;

    int sum=0;

    for(i=2;i<=n;i++)

    {

        min=INF;

        for(j=1;j<=n;j++)

            if(!vis[j]&&min>dis[j])

            {

                min=dis[j];

                p=j;

            }

            sum+=min;

            vis[p]=1;

            for(j=1;j<=n;j++)

            {

                if(!vis[j]&&dis[j]>map[p][j])

                    dis[j]=map[p][j];

            }

    }

    return sum;

}

int main()

{

    int n,i,j,d,d1;

    char c,c1;

    while(cin>>n&&n)

    {

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++)

                map[i][j]=INF;

        //while(n--&&cin>>c>>d)

        for(i=1;i<n;i++)

        {

            cin>>c>>d;

            for(j=1;j<=d;j++)

            {

                cin>>c1>>d1;

                map[c-'A'+1][c1-'A'+1]=d1;

                map[c1-'A'+1][c-'A'+1]=d1;

            }

        }

        //for(i=1;i<=n;i++,cout<<endl)

        //    for(j=1;j<=n;j++)

        //        cout<<map[i][j]<<" ";

        cout<<prim(n)<<endl;

    }

    return 0;

}
巴特西

hdu 1301

最新文章

热门文章
