洛谷P1525关押罪犯——二分做法

时间:2021-02-23 14:32:15

题目:https://www.luogu.org/problemnew/show/P1525

二分答案,二分图染色判断是否可行。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,ct,head[20005],ans,mx,mid;
bool col[20005],vis[20005];
struct N{
int to,next,w;
}edge[200005];
void add(int x,int y,int z)
{
ct++;
edge[ct].to=y;
edge[ct].next=head[x];
edge[ct].w=z;
head[x]=ct;
}
bool dfs(int x)
{
for(int i=head[x];i;i=edge[i].next)
{
int u=edge[i].to;
if(edge[i].w<=mid)continue;
if(!vis[u])
{
col[u]=!col[x];
vis[u]=1;
if(dfs(u))return 1;
}
else if(vis[u]&&col[u]==col[x])return 1;
}
return 0;
}
void per(int l,int r)
{
if(l>=r)//=!
{
ans=l;
return;
}
memset(col,0,sizeof col);
memset(vis,0,sizeof vis);
mid=(l+r)/2;
bool flag=0;
for(int i=1;i<=n;i++)
if(!vis[i])
{
vis[i]=1;col[i]=1;
if(dfs(i))
{
flag=1;
break;
}
}
if(flag)per(mid+1,r);
else per(l,mid);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);//无向边
mx=max(mx,z);
}
per(0,mx);
printf("%d",ans);
return 0;
}