Prim算法求权数和，POJ(1258)

题目链接：http://poj.org/problem?id=1258

解题报告：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <memory.h>

using namespace std;

#define N 10005
#define inf 100010

int a[N][N],ans;

bool vis[N];
int dis[N],n;

bool Prim()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
    }

    ans=0;dis[1]=0;

    for(int i=1;i<=n;i++)
    {
        int tmp=inf,k=0;

        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<tmp)
            {
                tmp=dis[j];
                k=j;
            }
        }

        if(tmp==inf)
        {
            return false;
        }

        vis[k]=true;
        ans+=tmp;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>a[k][j])
            {
                dis[j]=a[k][j];
            }
        }
    }
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }

        Prim();
        cout<<ans<<endl;
    }
    return 0;
}