题目：
提示：
Floyd最短路径算法实现(未测试)：
// // main.cpp // Alg_Floyd_playgame // // Created by wasdns on 16/11/19. // Copyright ? 2016年 wasdns. All rights reserved. // #include#include #include #include #include using namespace std; #define endless 1000000001; int Floydgh[5005][5005]; void Inigh(int n) { for (int i = 1; i <= n; i++) { Floydgh[i][i] = 0; for (int j = 1; j <= n; j++) { if (i != j) { Floydgh[i][j] = endless; } } } } void Creatgh(int n, int m) { Inigh(n); int i, u, v, w; for (i = 1; i <= m; i++) { cin >> u >> v >> w; Floydgh[u][v] = w; Floydgh[v][u] = w; } } void Alg_Floyd(int n) { int i, j, k; for (k = 1; k <= n; k++) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { int t = Floydgh[i][k] + Floydgh[k][j]; if (t < Floydgh[i][j]) { Floydgh[i][j] = t; Floydgh[j][i] = t; } } } } } int minjudge(int n) { int i, j; int minlen = endless; for (i = 1; i <= n; i++) { int cnt = 0; for (j = 1; j <= n; j++) { cnt += Floydgh[i][j]; } if (cnt < minlen) { minlen = cnt; } } return minlen; } int main() { int n, m; cin >> n >> m; Creatgh(n, m); Alg_Floyd(n); cout << minjudge(n) << endl; return 0; }
Prim生成树算法实现：
关于Prim算法，请参考我的另外一篇博客：
//// main.cpp// Prim//// Created by wasdns on 16/11/24.// Copyright © 2016年 wasdns. All rights reserved.//#include#include #include #include #include #include #define maxn 10000005;using namespace std;int Primgh[10000][10000];bool refer[10005];void Initial(int n, int m){ int i, j; for (i = 1; i <= n; i++) { refer[i] = false; for (j = 1; j <= n; j++) { if (i == j) { Primgh[i][j] = 0; } else Primgh[i][j] = maxn; } } int u, v, w; for (i = 1; i <= m; i++) { cin >> u >> v >> w; Primgh[u][v] = w; Primgh[v][u] = w; }}int Prim_Alg(int n, int m){ Initial(n, m); int i, j, k; int ans = 0; refer[1] = true; //起点为1 for (i = 1; i <= n-1; i++) { int minlen = maxn; int rcd = 1; for (j = 1; j <= n; j++) { if (!refer[j]) continue; int len1 = maxn; int rcd1 = 1; for (k = 1; k <= n; k++) { if (!refer[k]) { if (Primgh[j][k] < len1) { len1 = Primgh[j][k]; rcd1 = k; } } } if (len1 < minlen) { minlen = len1; rcd = rcd1; } } //char check = 'A'+rcd-1; //cout << "rcd: " << check << endl; //cout << "minlen: " << minlen << endl; refer[rcd] = true; rcd = 1; ans += minlen; } return ans;}int main(){ int n, m; cin >> n >> m; cout << Prim_Alg(n, m) << endl; return 0;}
测试样例：
/* eg1. Input: 4 6 1 2 1 2 3 2 1 3 3 2 4 3 3 4 5 1 4 4 Output: 6 eg2. Input: 7 11 1 2 7 1 4 5 2 4 9 2 3 8 2 5 7 3 5 5 4 5 15 4 6 6 5 6 8 5 7 9 6 7 11 Output: 39 */
2016/11/24