『算法-ACM 竞赛-图论』最小生成树-Prim 算法（带边输出）模板

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1005;
bool vis[maxn];
int cost[maxn][maxn], lowc[maxn];
vector<int> demo;
int prim(int cost[][maxn], int n)
{
int ans = 0;
memset(vis, false, sizeof(vis));
vis[0] = true;
for(int i = 1; i < n; ++i)
lowc[i] = cost[0][i];
for(int i = 1; i < n; ++i)
{
int minc = INF;
int p = -1;
for(int j = 0; j < n; ++j)
{
if(!vis[j] && minc > lowc[j])
{
minc = lowc[j];
p = j;
}
}
if(minc == INF)
return -1;
ans += minc;
demo.push_back(minc);
vis[p] = true;
for(int j = 0; j < n; ++j)
{
if(!vis[j] && lowc[j] > cost[p][j])
lowc[j] = cost[p][j];
}
}
return ans;
}

int main()
{
int n, m, u, v, w; //n 是顶点数，m 是边数
scanf("%d %d", &m, &n);
memset(cost, INF, sizeof(cost));
//memset(vis, 0 ,sizeof(vis));
for(int i = 0; i < m; ++i)
{
for(int j=0;j<m;j++)
{
cin>>cost[i][j];
cost[j][i]=cost[i][j];
}
}
//也可以通过边的数量输入数据 x y 之间有 z 长度的边，则连 cost[x][y]=z
prim(cost, m);
for(int i=0;i<m-1;i++) cout<<demo[i]<<" ";
return 0;
}