poj1258 AgriNet

用prim求最小生成树有点类似Dijkstra，把当前节点所联接的权重最小的边依次加入最小生成树中。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAXD 110
#define INF 0x3f3f3f3f
using namespace std;
int N,graph[MAXD][MAXD],res,key[MAXD];


void MST_PRIM()
{
    bool vis[MAXD];
    memset(vis,0,sizeof(vis));
    int k,i,t,w;
    for(i=1;i<=N;i++)
    key[i]=graph[1][i];
    vis[1]=true;
    res=0;
    for(k=1;k<N;k++)
    {
        w=INF,t=-1;
        for(i=1;i<=N;i++)
        {
            if(!vis[i]&&w>key[i])
            {
                w=key[i];
                t=i;
            }
        }
        vis[t]=true;
        res+=w;
        for(i=1;i<=N;i++)
        {
            if(!vis[i]&&key[i]>graph[t][i])
            {
                key[i]=graph[t][i];
            }
        }
    }
}
int main()
{
    //freopen("test.txt","r",stdin);
    while(scanf("%d",&N)!=EOF)
    {
        int i,j;
        memset(graph,0,sizeof(-1));
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=N;j++)
            {
                scanf("%d",&graph[i][j]);
            }
        }
        MST_PRIM();
        printf("%d\n",res);
    }
}