1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <algorithm> 8 #include <list> 9 #include <ctime> 10 #include <set> 11 #include <string.h> 12 #include <queue> 13 #include <cstdio> 14 using namespace std; 15 typedef int typec; // type of cost 16 const int V = 501; 17 const typec inf = 0x3f3f3f3f; // max of cost 18 #define CLR(arr, what) memset(arr, what, sizeof(arr)) 19 int vis[V]; 20 typec lowc[V]; 21 typec cost[V][V]; 22 typec prim(typec cost[][V], int n) { 23 int i, j, p; 24 typec minc, res = 0; 25 CLR(vis, 0); 26 vis[0] = 1; 27 for (i = 1; i < n; i++) 28 lowc[i] = cost[0][i]; 29 for (i = 1; i < n; i++) { 30 minc = inf; 31 p = -1; 32 for (j = 0; j < n; j++) 33 if (0 == vis[j] && minc > lowc[j]) { 34 minc = lowc[j]; 35 p = j; 36 } 37 if (inf == minc) 38 return -1; // 原图不连通 39 res += minc; 40 vis[p] = 1; 41 for (j = 0; j < n; j++) 42 if (0 == vis[j] && lowc[j] > cost[p][j]) 43 lowc[j] = cost[p][j]; 44 } 45 return res; 46 } 47 int dist(string& a, string& b) { 48 int res = 0; 49 for (int i = 0; i < 7; i++) { 50 res += (a[i] != b[i]); 51 } 52 return res; 53 } 54 inline void read(int& a) { 55 scanf("%d", &a); 56 } 57 int main() { 58 int abc, n; 59 cin >> abc; 60 string tmp; 61 while (abc--) { 62 CLR(cost, inf); 63 cin >> n; 64 for (int a = 0; a < n; a++) { 65 for (int b = 0; b < n; b++) { 66 read(cost[a][b]); 67 } 68 } 69 prim(cost, n); 70 int res = 0; 71 for (int a = 0; a < n; a++) { 72 res = max(res, lowc[a]); 73 } 74 cout << res << endl; 75 } 76 return 0; 77 }
最小生成树中最长的某条路径