洛谷 P1525. (模板题)关押罪犯
原题链接
简单
作者:
AC_5
,
2021-05-14 16:43:33
,
所有人可见
,
阅读 303
二分答案+二分图匹配
#include<bits/stdc++.h>
using namespace std;
const int INF=1e5+10;
struct node{
int to,ne,w;
}edge[2*INF];
int head[INF],vis[INF];
int n,m;
int tot=0;
void add(int u,int v,int w){
++tot;
edge[tot].to=v;
edge[tot].w=w;
edge[tot].ne=head[u];
head[u]=tot;
}
bool bfs(int x,int w){
queue<int>q;
q.push(x);
vis[x]=1;
while(q.size()){
int now=q.front();
q.pop();
for(int i=head[now];~i;i=edge[i].ne){
int to=edge[i].to;
int nw=edge[i].w;
if(nw<=w) continue;
if(vis[to]==0){
if(vis[now]==1) vis[to]=-1;
else vis[to]=1;
q.push(to);
}
else{
if(vis[to]==vis[now]) return false;
}
}
}
return true;
}
bool check(int x){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
if(vis[i]==0){
if(!bfs(i,x)){
return false;
}
}
}
return true;
}
int main(){
cin>>n>>m;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
int l=0,r=1e9;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}