UVa 11747

　　题目大意：计算最小生成树有两种算法：一种是kruskal算法，另一种是与之相反的：如果图中存在环，去掉权重最大的边，直到不存在环。输出去掉的那些边。

　　可以用kruskal算法解决，在判断一条边时如果加入该边能形成环，保存该边即可。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MAXN 1100
 6 typedef pair<int, int> ii;
 7 
 8 int p[MAXN];
 9 
10 int find(int x)
11 {
12     return p[x] == x ? x : p[x]=find(p[x]);
13 }
14 
15 int main()
16 {
17 #ifdef LOCAL
18     freopen("in", "r", stdin);
19 #endif
20     int n, m;
21     while (scanf("%d%d", &n, &m) && (n || m))
22     {
23         int u, v, w;
24         vector<pair<int, ii> > EdgeList;
25         for (int i = 0; i < m; i++)
26         {
27             scanf("%d%d%d", &u, &v, &w);
28             EdgeList.push_back(make_pair(w, make_pair(u, v)));
29         }
30         sort(EdgeList.begin(), EdgeList.end());
31         for (int i = 0; i < n; i++)
32             p[i] = i;
33         vector<int> ans;
34         for (int i = 0; i < EdgeList.size(); i++)
35         {
36             w = EdgeList[i].first;
37             u = EdgeList[i].second.first;
38             v = EdgeList[i].second.second;
39             int pu = find(u);
40             int pv = find(v);
41             if (pu != pv)  p[pv] = pu;
42             else  ans.push_back(w);
43         }
44         if (ans.empty())  printf("forest
");
45         else
46         {
47             for (int i = 0; i < ans.size(); i++)
48                 printf("%s%d", i == 0 ? "" : " ", ans[i]);
49             printf("
");
50         }
51     }
52     return 0;
53 }

View Code