并查集 / 二分图
二分图在下面
并查集
总体思路
从大到小处理，将罪犯间的敌人关系作为维护对象和并连条件，即敌人的敌人是朋友。由于我们的kruskal是大顶堆的，所以在得到第一个权值的时候就结束循环了。
具体实现
开一个enemy的数组，处理两个人时先看他们是否已经被迫呆在一起，如果是，那他们的仇恨值会是最大的，这就是我们要的答案了。再看\(a\)有没有敌人，有则说明有仇恨值更大的人---\(b\)，已经被分到了\(a\)的对面，新进来的人必须和\(b\)呆在一起。没有则把他们的enemy数组更新
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 2e4 + 10;
constexpr int maxm = 2e5 + 10;typedef struct node
{int x,y,w;bool operator<(const node& other)const{return w>other.w;}
}node;node nodes[maxm];
int fa[maxn],enemy[maxn];int fnd_root(int x)
{int r=x;while (fa[r]!=r) r = fa[r];int j=x,tmp;while (j!=r){tmp = fa[j];fa[j]=r;j=tmp;}return r;
}void join(int x,int y)
{int xr = fnd_root(x),yr = fnd_root(y);if(xr!=yr){fa[xr] = yr;}
}void init (int n)
{for (int i=1;i<=n;++i){fa[i] = i;}
}signed main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endif // ONLINE_JUDGEint n,m,ans=0;scanf("%lld%lld",&n,&m);init(n);for (int i=1;i<=m;++i){scanf("%lld%lld%lld",&nodes[i].x,&nodes[i].y,&nodes[i].w);}sort(nodes+1,nodes+1+m);for (int i=1;i<=m;++i){if (fnd_root(nodes[i].x)!=fnd_root(nodes[i].y))// 没被安排在一起{if (enemy[nodes[i].x]!=0)//已经标记过敌人，就加一起{join(enemy[nodes[i].x],nodes[i].y);}else//没有则标记{enemy[nodes[i].x]=nodes[i].y;}if(enemy[nodes[i].y]!=0){join(enemy[nodes[i].y],nodes[i].x);}else{enemy[nodes[i].y]=nodes[i].x;}}else{ans = nodes[i].w;break;}}printf("%lld",ans);return 0;
}二分图
思路
由于所有罪犯被分到了两个监狱，所以我们很自然地想到二分图，但我们很难知道我们的图在什么时候刚好不构成二分图，但我们可以知道大于某长度的边能不能构成二分图，利用二分就可以快速找到刚好不构成二分图的长度——答案。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 2e4+10;
constexpr int maxm = 2e5+10;typedef struct edge
{int to,nex,wei;
}edge;edge edges[maxm];
int heads[maxn],enums;
int color[maxn];// 0:未染色, 1:监狱A, 2:监狱B
int n,m;void add_edge(int x,int y,int w)
{++enums;edges[enums].to=y;edges[enums].nex=heads[x];edges[enums].wei=w;heads[x]=enums;
}bool dfs(int u,int c,int mid)
{color[u]=c;for(int i=heads[u]; i; i=edges[i].nex){int v=edges[i].to;int w=edges[i].wei;if(w<=mid){continue;}if(!color[v]){if(!dfs(v,3-c,mid)) // 传递不合法状态{return 0;}}else if(color[v]==c)// 不合法{return 0;}}return 1;
}bool check(int x)
{memset(color,0,sizeof(color)); // 要初始化for(int i=1;i<=n;++i){if(!color[i])// 可能不联通{if(!dfs(i,0,x)){return 0;}}}return 1;
}int binans(int l,int r)
{int mid;while(l<=r){mid=l+((r-l)>>1);if(check(mid)){r=mid-1;}else{l=mid+1;}}return l;
}signed main()
{scanf("%lld%lld",&n,&m);int u,v,w;int ma_fen=0;for(int i=1;i<=m;++i){scanf("%lld%lld%lld",&u,&v,&w);add_edge(u,v,w); // 双向add_edge(v,u,w);ma_fen=max(ma_fen,w);}int ans = binans(0,ma_fen);// 最小可能是0，最大一定小于最大原值printf("%lld\n",ans);return 0;
}