NOIP2010关押罪犯二分+二染色

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这个题一上来没有思路，后来想没有思路就二分吧

那么我们来二分

首先，大于当前的mid值的关系，不能出现在一个集合里

（即关系形成的图是一个二分图，判定二分图可以二染色）

如果不能形成二分图，那么说明有些关系要在一个集合里，那就向上二分

否则向下二分

#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int N=2e4+;
const int INF=0x3f3f3f3f;
int head[N],tot,n,m;
struct Edge
{
int u,v,next;
bool operator<(const Edge &rhs)const
{
return next<rhs.next;
}
} edge[N*],o[N*];
void add(int u,int v)
{
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
int cur[N];
bool dfs(int u,int f)
{
cur[u]=(cur[f]^);
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].v;
if(v==f||cur[v]==(cur[u]^))continue;
if(cur[v]==cur[u])return false;
if(!dfs(v,u))return false;
}
return true;
}
bool judge(int x)
{
Edge tmp;
tmp.next=x;
int pos=upper_bound(o+,o++m,tmp)-o;
if(pos>m)return true;
memset(head,-,sizeof(head)),tot=;
memset(cur,-,sizeof(cur));
int s;
for(int i=pos; i<=m; ++i)
add(o[i].u,o[i].v),add(o[i].v,o[i].u),s=o[i].u;
for(int i=pos;i<=m;++i){
int s=o[i].u;
if(cur[s]!=-)continue;
cur[s]=;
if(!dfs(s,s))return false;
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
if(m==)
{
printf("0\n");
return ;
}
for(int i=; i<=m; ++i)
scanf("%d%d%d",&o[i].u,&o[i].v,&o[i].next);
o[].next=;
sort(o+,o++m);
int l=,r=m;
while(l<r)
{
int mid=(l+r)>>;
if(judge(o[mid].next))r=mid;
else l=mid+;
}
printf("%d\n",o[(l+r)>>].next);
return ;
}