题意：有n个点，部分点之间可以连接无向边，每条可以连接的边都有一个权值。求一种连接方法将这些点连接成一个连通图，且所有连接了的边中权值最大的边权值最小。
解法：水题，直接用Kruskal算法做一遍就行了，不过还是应该仔细想想为什么Kruskal可行。原因是，在从小边往大边遍历的过程中(一直保持图为连通图)，若判定某边i必须被连接，则因为图是连通图，所以连接比它小的边不可能使边i不需要连接，所以，要使边i不需要连接，必须连接比它大的边，根据题目要求，还是连接边i情况更优。
tag：最小生成树
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-24 20:57 4 * File Name: G-POJ-1861.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 #include <vector> 11 12 using namespace std; 13 14 #define CLR(x) memset(x, 0, sizeof(x)) 15 #define PB push_back 16 const int maxm = 15005 * 2; 17 const int maxn = 1005; 18 19 struct pat{ 20 int s, t, l; 21 }; 22 23 pat p[maxm]; 24 bool v[maxm]; 25 vector<int> ans; 26 int n, m, all, f[maxn]; 27 28 bool cmp(pat a, pat b) 29 { 30 return a.l < b.l; 31 } 32 33 void init() 34 { 35 int t1, t2, t3; 36 all = 0; 37 for (int i = 0; i < m; ++ i){ 38 scanf ("%d%d%d", &t1, &t2, &t3); 39 -- t1; -- t2; 40 p[all].s = p[all+1].t = t1; 41 p[all].t = p[all+1].s = t2; 42 p[all++].l = t3; 43 p[all++].l = t3; 44 } 45 } 46 47 void Kruskal() 48 { 49 sort(p, p+all, cmp); 50 for (int i = 0; i < n; ++ i) f[i] = i; 51 CLR (v); 52 for (int i = 0; i < all; ++ i){ 53 int t1 = p[i].s, t2 = p[i].t; 54 while (t1 != f[t1]) t1 = f[t1]; 55 while (t2 != f[t2]) t2 = f[t2]; 56 if (t1 != t2){ 57 v[i] = 1; 58 f[t1] = t2; 59 } 60 } 61 } 62 63 int main() 64 { 65 while (scanf ("%d%d", &n, &m) != EOF){ 66 init(); 67 Kruskal(); 68 69 ans.clear(); 70 int cnt = 0; 71 for (int i = 0; i < all; ++ i) if (v[i]){ 72 cnt = max(i, cnt); 73 ans.PB(i); 74 } 75 int sz = ans.size(); 76 printf ("%d %d ", p[cnt].l, sz); 77 for (int i = 0; i < sz; ++ i) 78 printf ("%d %d ", p[ans[i]].s+1, p[ans[i]].t+1); 79 } 80 return 0; 81 }