题意：有一个旅游区，旅游区有很多的景点，景点间需要开通缆车，使得任意两个景点可以互相到达。现在给出一些点间的缆车线路制造成本，两个景点之间可能有多重制造方式。问最少的花费是多少。
分析：连通+最少的花费 = 最小生成树。
Prim算法适用于稠密图, Kruskal适用于稀疏图
- 好家伙，两个 runtime-error
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N =210, INF = 0x3f3f3f3f;
int n, m, p, g[N][N];
struct T {
int u, v, w;
T(int a = 0, int b = 0, int c = 0) : u(a), v(b), w(c) {}
bool operator<(const T& r) const { return w < r.w; }
} e[N*N];
int dis[N];
bool st[N];
int prim() {
memset(dis, 0x3f, sizeof(dis));
memset(st, 0, sizeof(st));
int ans = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++)
if (!st[j] && (u == -1 || dis[u] > dis[j]))
u = j;
if (u && dis[u] == INF) return -1;
if (u) ans += dis[u];
for (int j = 0; j < n; j++)
dis[j] = min(dis[j], g[u][j]);
st[u] = 1;
}
return ans;
}
int f[N];
int find(int u) {
return u == f[u] ? u : f[u] = find(f[u]);
}
int kruskal() {
int ans = 0, cnt = 0;
for (int i = 0; i <= n; i++)
f[i] = i;
sort(e + 1, e + 1 + p);
for (int i = 1; i <= p; i++) {
int fu = find(e[i].u), fv = find(e[i].v);
if (fu != fv) f[fu] = f[fv], ans += e[i].w, cnt++;
if (cnt == n - 1) break;
}
return cnt == n - 1 ? ans : -1;
}
int main() {
char u, v;
int w, t;
while (~scanf("%d\n", &n) && n) {
memset(g, 0x3f, sizeof(g));
p = 0, t = n - 1;
while (t--) {
scanf("%c%d", &u, &m), u -= 'A';
for (int i = 1; i <= m; i++) {
scanf(" %c%d", &v, &w), v -= 'A';
g[u][v] = g[v][u] = min(g[u][v], w);
e[++p] = T(u, v, w);
}
getchar(); // \n
}
printf("%d\n", prim());
// printf("%d\n", kruskal());
}
return 0;
}