题目大意： 有一个岛国，没有高速公路，交通非常困难。政府意识到了这一问题，他们计划建造一些高速公路，这样可以使任何一对城镇都不离开公路系统。所有公路都是沿直线建造并且是双向的。政府想降低花费，所以想找到一种建造方案，能连接所有的城镇，并且公路的总长度最小。注意题目求的是最小生成树最长的那条边。
#include <cstdio> #include <cstring> #include <algorithm> #define N 600 #define INF 0x3f3f3f3f int dist[N][N]; int lostcow[N], used[N]; int prim(int n) { int i, j, k, sum = 0, min; memset(used, 0, sizeof(used)); for(i = 1; i <= n; i++) lostcow[i] = dist[1][i]; used[1] = 1; for(i = 1; i <= n - 1; i++) { k = 1; min = INF; for(j = 1; j <= n; j++) if(!used[j] && lostcow[j] < min) { min = lostcow[j]; k = j; } if(sum < min)/* 这与最小生成树不一样不是求相加之和 */ sum = min; used[k] = 1; for(j = 1; j <= n; j++) if(!used[j] && dist[k][j] < lostcow[j]) lostcow[j] = dist[k][j]; } return sum; } int main() { int n; scanf("%d", &n); while(n--) { int m, i, j; scanf("%d", &m); for(i = 1; i <= m; i++) for(j = 1; j <= m; j++) scanf("%d", &dist[i][j]); int s = prim(m); printf("%d\n", s); } return 0; }
原文：http://www.cnblogs.com/yu0111/p/4816906.html