题意：给一张无向图，若存在圈则输出每个圈上最大的边的权值。
思路：题目的提示已经很明显了，求最小生成树可以用破圈发，每次删去圈上最大的那条边。那么反过来说圈上最大的边就是最小生成树中没有出现的那些边了。所以我们求完最小生成树，然后把边标记一下，然后剩下来的输出就行了。
代码如下：
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 }