首先把本题抽象一下,把犯人看成点,把冲突影响力看成边,转化成图论问题
可以推断出答案是[0,1e9]中的某个点,答案区间具有二段性,想一个性质可以把区间分成两段,这个性质是大于x的边都在监狱两边。
其实也就是,二分查找一个答案,把图中小于等于这个边的视为没有边,看是否是个二分图。
//把问题抽象一下,把监狱看成点集,把冲突影响力看成边,问题就抽象成两个点集和边的问题
//这里把小于x的边看成没有,检查是否是二分图,如果是二分图,就继续二分,直到找到
//二分右部分左边界
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=20010;
const int M=200010; //把无向边看成有向边,因为染色过程中,多加一条边无实际意义
int n,m; //n个点m条无向边
int h[N],e[M],ne[M],w[M],idx; //邻接表
int color[N]; //0表示没搜索过,1表示染黑色,2表示染红色
//邻接表加边函数
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
bool dfs(int u,int sum,int st){
color[u]=3-st;
//遍历所有边
for(int i=h[u];i!=-1;i=ne[i]){
int a=e[i],b=w[i];
//如果边权小于等于sum,视为没有边
if(b<=sum)continue;
//如果边权大于sum
//如果没有搜索过
if(!color[a]){
if(!dfs(a,sum,3-st))return false;
}else{
if(color[a]==color[u])return false;
}
}
return true;
}
//检查是否是二分图
bool check(int sum){
//每次重置颜色数组
memset(color,0,sizeof color);
for(int i=1;i<=n;i++){
if(!color[i]){
if(!dfs(i,sum,1))return false;
}
}
return true;
}
int main(){
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
//二分
int l=0,r=1e9;
while(l<r){
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}