关押罪犯

题目地址：http://www.51cpc.com/web/problem.php?id=4261

Summarize：

　此题最巧妙的是“敌人的敌人就是朋友！”，故需先将敌对关系放入优先队列，按怨恨值从大到小排序，建一个数组存储对应敌对关系，

　当遇到第二个以及后来的敌人时，将之前的敌人与后来的敌人放进一个监狱，直到遇见一对关系中两人已经关在统一监狱，即为最大值。

附代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<queue>
 8 #include<cmath>
 9 using namespace std;
10 
11 #define LL long long
12 const int N = 2e4+5;
13 int n,m, f[N], enemy[N];
14 struct RELA {
15     LL a, b, value;
16     friend bool operator<(const struct RELA &x, const struct RELA &y) {
17         return x.value<y.value;
18     }
19 };
20 
21 int find(int x) {
22     if(x != f[x])
23         f[x] = find(f[x]);
24     return f[x];
25 }
26 
27 bool Union(int a, int b) {
28     int x = find(a);
29     int y = find(b);
30     if(x == y) return false;
31     if(x != y) f[x]=y;
32     return true;
33 }
34 
35 int main()
36 {
37     ios::sync_with_stdio(false);
38     
39     while(cin>>n>>m)
40     {
41         LL a,b,value;
42         priority_queue<RELA> rela;
43         for(int i=1; i<=n; i++)
44             f[i]=i, enemy[i]=0;
45         for(int i=0; i<m; i++) {
46             cin>>a>>b>>value;
47             rela.push(RELA{a,b,value});
48         }
49         
50         bool can=true;
51         while(!rela.empty()) {
52             RELA t = rela.top();
53             rela.pop();
54             a=t.a, b=t.b, value=t.value;
55             
56             if(!enemy[a]) enemy[a]=b;
57             else Union(enemy[a],b);
58             if(!enemy[b]) enemy[b]=a;
59             else Union(enemy[b],a);
60             
61             if(find(a) == find(b)) {
62                 can=false;
63                 cout<<value<<endl;
64                 break;
65             }
66         }
67         if(can) cout<<0<<endl;
68     }
69 }