算法:$prime$ 算法
时间复杂度:$O(n^2 + m)$
因为 $n$ 比较小,应该是一个稠密图,用 $prime$ 算法
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n;
int g[N][N], dist[N];
bool st[N];
int prime()
{
memset(dist, 0x3f, sizeof(dist));
int res = 0;
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 1; j <= n; ++j) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
if (i) res += dist[t];
for (int j = 1; j <= n; ++j) {
dist[j] = min(dist[j], g[t][j]);
}
st[t] = true;
}
return res;
}
int main()
{
cin >> n;
memset(g, 0x3f, sizeof(g));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int w;
cin >> w;
g[i][j] = w;
}
}
int t = prime();
cout << t << endl;
return 0;
}