算法
(Prim) $O(n^2)$
可以引入超级源点来解决,然后把任意两点连边求一遍最小生成树即可。注意到,这个是稠密图,所以 $\rm Prim$ 效率会比较高。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 305;
const int INF = 1e9;
int n;
int adj[N][N];
int cost[N];
bool vis[N];
int prim() {
for (int i = 0; i <= n + 1; ++i) {
cost[i] = INF;
vis[i] = 0;
}
cost[1] = 0;
int res = 0;
for (int i = 0; i < n + 1; ++i) {
// 寻找cost[index]最小的实点index
int index = 0;
for (int j = 1; j <= n + 1; ++j) {
if (vis[j] == 0 and cost[j] < cost[index]) {
index = j;
}
}
vis[index] = 1; // 把实点变成虚点
res += cost[index]; // 累加权值
// 修改与index相连的所有实点
for (int j = 1; j <= n + 1; ++j) {
if (vis[j] == 0 and cost[j] > adj[index][j]) {
cost[j] = adj[index][j];
}
}
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
int w; cin >> w;
adj[n + 1][i] = adj[i][n + 1] = w;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> adj[i][j];
}
}
int ans = prim();
cout << ans << '\n';
return 0;
}