题目描述
(自己看吧懒得复制。。。)
Prim算法例题
样例
输入
3
0 1 2
1 0 1
2 1 0
输出
2
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int g[101][101], minn[101]; //minn[i]可加入点的最小边权
bool u[101]; //1为连接的点,0为未连接的点
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> g[i][j]; //输入i到j的边权
memset(minn, 0x7f, sizeof(minn)); //初始最小边权最大
minn[1] = 0; //第一个点到自己距离为0
memset(u, 1, sizeof(u)); //初始所有点都未连接
for(int i = 1; i <= n; i++){
int k = 0;
for(int j = 1; j <= n; j++)
if(u[j] && (minn[j] < minn[k])) k = j; //从未连接点中找最小边权的点
u[k] = 0; //找到后连接(这里没特判找不到的情况,这题也没用到)
for(int j = 1; j <= n; j++)
if(u[j] && (g[k][j] < minn[j])) minn[j] = g[k][j]; //修改已连接点间的最小边权
}
int ans = 0;
for(int i = 1; i <= n; i++) ans += minn[i]; //最小权值累加
cout << ans << endl;
return 0;
}