poj1258 最小生成树裸题 给个模板看就行了

直接给你邻接矩阵，一定是稠密图，所以优先选择pirm。

然后AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;

int mp[maxn][maxn];
int dis[maxn];
int N;
bool in[maxn];

int prim()
{
    memset(in,0,sizeof(in));
    for(int i=1;i<=N;i++)
        dis[i]=mp[1][i];
    in[1]=1;


    int ans=0;
    for(int i=2;i<=N;i++)
    {
        int minn=inf,r;
        for(int j=1;j<=N;j++)
        {
            if(!in[j]&&minn>dis[j])
            {
                minn=dis[j];
                r=j;
            }
        }

        ans+=minn;

        in[r]=1;
        for(int j=1;j<=N;j++)
            if(!in[j]&&dis[j]>mp[r][j])
               dis[j]=mp[r][j];
    }
    return ans;
}

int main()
{
    while(scanf("%d",&N)==1&&N)
    {

        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                scanf("%d",&mp[i][j]);

        printf("%d\n",prim());
    }
}

要输出的是所要的边的总和。

和dijstra很像只不过dis数组意义不一样，所以松弛那块地方也不一样。