题意：FJ想连接光纤在各个农场以便网络普及，现给出一些连接关系（给出邻接矩阵），从中选出部分边，使得整个图连通。求边的最小总花费。
思路：裸的最小生成树，本题为稠密图，Prim算法求最小生成树更优，复杂度O(n^2)
prim：
#include#include #include #include 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#include #include #include 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;}