跟P1892团伙的做法类似。
除了用数组保存敌人编号之外，还有另一种做法。
团伙：合并时，用i节点表示为友，i+n结点表示为敌。
本题：合并时，用i节点表示同一监狱，i+n结点表示不同监狱。
按边权从大到小枚举边，贪心地把边连接的两个结点设定为不同监狱（为敌）
遇到冲突后说明必须在同一个监狱，此时输出权值，即为冲突的最大值。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,cnt,fa[100005],ans;
struct edge{
int u,v,w;
}e[100005];
inline void add(int u,int v,int w){
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
}
inline int cmp(edge x,edge y){
return x.w>y.w;
}
inline int getfa(int v){
if(fa[v]==v)return v;
fa[v]=getfa(fa[v]);
return fa[v];
}
inline void merge(int x,int y){
x=getfa(x);y=getfa(y);
fa[y]=x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=2*n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;i++){
int u=e[i].u,v=e[i].v;
int fau=getfa(u),fav=getfa(v);
if(fau!=fav){
merge(u,v+n);
merge(v,u+n);
}
else{
printf("%d
",e[i].w);
return 0;
}
}
printf("0
");//洛谷第一个点卡0
}