NOIP 2010 提高组 复赛 第三题 关押罪犯 prison AC代码(并查集 敌人的敌人是朋友)

NOIP 2010 提高组 复赛 第三题   关押罪犯  prison  AC代码(并查集 敌人的敌人是朋友)

总目录详见：NOIP 提高组 复赛 试题 目录 信奥 历年

在线测评地址：https://www.luogu.com.cn/problem/P1525

AC代码(并查集 敌人的敌人是朋友)

样例模拟如下：

输入：
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
输出：
3512按怨气自大到小排序
1 2 28351
3 4 12884
1 3 6618
2 3 3512
1 4 2534
2 4 1805敌人的敌人是朋友
1 2 28351
(1,2+4=6),(2,1+4=5)
3 4 12884
(3,4+4=8),(4,3+4=7)
1 3 6618
(1,3+4=7),(3,1+4=5)
综合之前情况，变为
(1,7,4),(3,5,2)
冲突发生在2 3 3512

AC代码(并查集 敌人的敌人是朋友) 如下：

#include <bits/stdc++.h>
#define maxm 100010
#define maxn 20010
using namespace std;
struct node{int a,b,c;
}q[maxm];
int n,m,f[maxn*2];
int cmp(node a,node b){return a.c>b.c;
}
int getf(int u){return f[u]==u?u:f[u]=getf(f[u]);
}
int main(){int i,f1,f2;scanf("%d%d",&n,&m);for(i=1;i<=2*n;i++)f[i]=i;for(i=1;i<=m;i++)scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c);sort(q+1,q+1+m,cmp);for(i=1;i<=m;i++){f1=getf(q[i].a),f2=getf(q[i].b);if(f1==f2){printf("%d\n",q[i].c);return 0;}f[f2]=getf(q[i].a+n);f[f1]=getf(q[i].b+n);}printf("0\n"); return 0;
}