题意：给你一张无向带权图，求出最小生成树和次小生成树。
思路：数据小直接爆。枚举删除最小生成树上的每一条边。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-05 20:31 5 * Filename : uva_10600.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 1001; 34 struct edge{ 35 int fr, to, val; 36 }e[LEN*LEN]; 37 int n, m, parent[LEN], vis[LEN*LEN]; 38 39 bool cmp(edge a, edge b){return a.val < b.val;} 40 void init(){for(int i=0; i<LEN; i++) parent[i] = i;} 41 int Find(int x){return parent[x] == x? x: parent[x] = Find(parent[x]);} 42 43 int kruskal(int pos){ 44 int cnt = 0, ret = 0; 45 for(int i=0; i<m; i++){ 46 if(i == pos) continue; 47 int pa = Find(e[i].fr), pb = Find(e[i].to); 48 if(pa == pb) continue; 49 parent[pa] = pb; 50 if(pos < 0)vis[i] = 1; 51 ret += e[i].val; 52 cnt ++; 53 if(cnt == n-1) break; 54 } 55 if(cnt!=n-1) return INF; 56 return ret; 57 } 58 59 int main() 60 { 61 // freopen("in.txt", "r", stdin); 62 63 int a, b, v, T; 64 scanf("%d", &T); 65 while(T--){ 66 init(); 67 scanf("%d%d", &n, &m); 68 for(int i=0; i<m; i++) 69 scanf("%d%d%d", &e[i].fr, &e[i].to, &e[i].val); 70 sort(e, e+m, cmp); 71 memset(vis, 0, sizeof vis); 72 printf("%d ", kruskal(-1)); 73 int ans = INF; 74 for(int i=0; i<m; i++) 75 if(vis[i]) { 76 init(); 77 ans = min(ans, kruskal(i)); 78 } 79 printf("%d ", ans); 80 } 81 return 0; 82 }