NOIP 2010 关押罪犯

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct c{
 5     int x,y,z;
 6 }f[100005];
 7 int n, m, a[20005], b[20005];
 8 bool cmp(c a,c b){
 9     return a.z>b.z;
10 }
11 int find(int x){
12     if(a[x]==x) return x;
13     a[x]=find(a[x]);
14     return a[x];
15 }
16 void ad(int x,int y){
17     x=find(a[x]);
18     y=find(a[y]);
19     a[x]=y;
20 }
21 bool check(int x,int y){
22     x=find(x);
23     y=find(y);
24     if(x==y) return true;
25     return false;
26 }
27 int main(){
28     scanf("%d%d",&n,&m);
29     for(int i=1; i<=n; i++) a[i]=i;
30     for(int i=1; i<=m; i++)
31         scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);
32     sort(f+1,f+m+1,cmp);
33     for(int i=1; i<=m+1; i++){
34         if(check(f[i].x,f[i].y)){
35             printf("%d",f[i].z);
36             break;
37         }
38         else{
39             if(!b[f[i].x]) b[f[i].x]=f[i].y;
40             else    ad(b[f[i].x], f[i].y);
41             if(!b[f[i].y]) b[f[i].y]=f[i].x;
42             else    ad(b[f[i].y], f[i].x);
43         }
44     }
45     return 0;
46 }