uva 11747(kruskal 变形)

题意:给一张无向图,若存在圈则输出每个圈上最大的边的权值。

思路:题目的提示已经很明显了,求最小生成树可以用破圈发,每次删去圈上最大的那条边。那么反过来说圈上最大的边就是最小生成树中没有出现的那些边了。所以我们求完最小生成树,然后把边标记一下,然后剩下来的输出就行了。

代码如下:

uva 11747(kruskal 变形)
 1 /**************************************************
 2  * author     : xiaohao z
 3  * blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * last modified : 2014-02-05 17:42
 5  * filename     : uva_11747.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 int n, m, parent[len], tag[len*len];
35 struct edge{
36      int fr, to, val;
37 }e[len*len];
38 bool cmp(edge a, edge b){return a.val < b.val;}
39 int find(int x){ return parent[x] == x?x:parent[x] = find(parent[x]);}
40 
41 void kruskal(){
42     memset(tag, 0, sizeof tag);
43     for(int i=0; i<len; i++) parent[i] = i;
44     sort(e, e+m, cmp);
45     int i, cnt = 0;
46     for(i=0; i<m; i++){
47          int pa = find(e[i].fr), pb = find(e[i].to);
48          if(pa == pb) continue;
49          tag[i] = 1;
50          parent[pa] = pb;
51          cnt++;
52          if(cnt == n-1) break;
53     }
54     int f = 1;
55     for(int i=0; i<m; i++){
56         if(tag[i]) continue;
57         if(f) f=0;
58         else printf(" ");
59         printf("%d", e[i].val);
60     }
61     if(f) printf("forest");
62     puts("");
63 }
64 
65 int main()
66 {
67 //    freopen("in.txt", "r", stdin);
68 
69     while(scanf("%d%d", &n, &m)!=EOF){
70         if(!n && !m) break;
71         for(int i=0; i<m; i++)
72              scanf("%d%d%d", &e[i].fr, &e[i].to, &e[i].val);
73         kruskal();
74     }
75     return 0;
76 }
View Code

uva 11747(kruskal 变形)

上一篇:剑指Offer - 九度1356 - 孩子们的游戏(圆圈中最后剩下的数)


下一篇:Hadoop常见问题