题意：FJ想连接光纤在各个农场以便网络普及，现给出一些连接关系（给出邻接矩阵），从中选出部分边，使得整个图连通。求边的最小总花费。
思路：裸的最小生成树，本题为稠密图，Prim算法求最小生成树更优，复杂度O(n^2)
prim：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> using namespace std; int mat[110][110];
bool vis[110];
int d[110]; int Prim(int n) {
int ans = 0;
int p = 0;
vis[0] = 1;
for (int j = 1; j < n; ++j) {
d[j] = mat[p][j];
}
for (int i = 1; i < n; ++i) {
p = -1;
for (int j = 1; j < n; ++j) {
if (vis[j]) continue;
if (p == -1 || d[j] < d[p]) {
p = j;
}
}
ans += d[p];
vis[p] = 1;
for (int j = 1; j < n; ++j) {
if (vis[j]) continue;
d[j] = min(d[j], mat[p][j]);
}
}
return ans;
} int main() {
int n, i, j;
while (scanf("%d", &n) != EOF) {
memset(vis, 0, sizeof(vis));
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
scanf("%d", &mat[i][j]);
}
}
int ans = Prim(n);
printf("%d\n", ans);
}
return 0;
}
kruskal：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> using namespace std; int N; // 节点数量
struct edge {
int from, to, dist;
bool operator<(const edge &b) const {
return dist < b.dist;
}
} es[10006];
int par[105];
void init() {
for (int i = 1; i <= N; ++i) par[i] = i;
}
int find(int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) par[x] = y;
}
int kruskal() {
int res = 0;
init();
int E = N*N;
sort(es + 1, es + 1 + E);
for (int i = 1; i <= E; ++i) {
edge e = es[i];
//printf("u:%d v:%d d:%d\n", e.from, e.to, e.dist);
if (find(e.from) != find(e.to)) {
unite(e.from, e.to);
res += e.dist;
}
}
return res;
}
void solve() {
cout << kruskal() << endl;
}
int main()
{
while (cin >> N) {
int d;
int id;
for (int u = 1; u <= N; ++u)
for (int v = 1; v <= N; ++v) {
cin >> d;
id = (u - 1)*N + v;
es[id].from = u;
es[id].to = v;
es[id].dist = d;
}
solve();
}
return 0;
}