POJ1258 最小生成树prim算法

典型的prim算法

这类题目可以稍作变形，比如POJ2421

#include <iostream>
#include <map>
#define MAXN 102
typedef long elem_t;
using namespace std;
elem_t prim(int n,elem_t mat[MAXN][MAXN]){
    elem_t closeEdge[MAXN],sum=0,min;
    int i,j,k;
    for(i = 0; i < n; i++)
        closeEdge[i] = mat[0][i];//初始化辅助数组
    for(i = 1; i < n; i++)
    {
        j = 0;
        while(!closeEdge[j])j++;//寻找第一个未归入的点
        min = closeEdge[j];k = j;
        //开始寻找下一节点
        for(j++; j < n; j++)
            if(closeEdge[j] && min > closeEdge[j])
            {
                min = closeEdge[j];
                k = j;
            }
        sum += closeEdge[k];
        closeEdge[k] = 0;
        for(j = 0; j < n; j++)//新顶点入集并重新选择最小边
            if(mat[k][j] && mat[k][j] < closeEdge[j])
                closeEdge[j] = mat[k][j];
                
    }
    return sum;
}

int main(){
    int n,i,j;
    long result;
    long distance[MAXN][MAXN];
    while(cin>>n){
        for (i = 0;i < n;i++)
            for (j = 0;j < n;j++){
                    cin>>distance[i][j];
                }
        result  = prim(n,distance);
        cout<<result<<endl;
    }
    return 0;
}