noip 2010 关押罪犯 （二分图染色 并茶几）

/*

二分图染色版本

两个监狱对应二部图的两部分

在给定的怨气值里二分

对于每一个Ci 进行染色判断是否合法

染色的时候 如果这条边的ci > Ci 这两个人就带分开 即染成不同的颜色

如果染色到某两个点颜色相同且怨气值>Ci 这个Ci就不合法

二分直到最后答案

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100010

using namespace std;

int n,m,num,head[maxn],Ci,ans,color[maxn];

struct node

{

    int v,t,pre;

}e[maxn*];

struct nope

{

    int x,y,z;

}p[maxn];

int cmp(const nope &a,const nope &b)

{

    return a.z<b.z;

}

void Add(int from,int to,int dis)

{

    num++;

    e[num].t=dis;

    e[num].v=to;

    e[num].pre=head[from];

    head[from]=num;

}

bool Color(int s)

{

    for(int i=head[s];i;i=e[i].pre)

      if(e[i].t>Ci)

          {

            if(color[s]==color[e[i].v])return ;

            if(color[e[i].v]==)

                {

                  color[e[i].v]=-color[s];

                  if(!Color(e[i].v))return ;

            }

        }

    return ;

}

bool pd()

{

    for(int i=;i<=n;i++)

      if(color[i]==)

        {

          color[i]=;

          if(!Color(i))return ;

        }

    return ;

}

int main()

{

    scanf("%d%d",&n,&m);

    int u,v,t;

    for(int i=;i<=m;i++)

      {

          scanf("%d%d%d",&u,&v,&t);

          p[i].x=u;p[i].y=v;p[i].z=t;

          Add(u,v,t);Add(v,u,t);

      }

    sort(p+,p++m,cmp);

    int l=,r=m;

    while(l<=r)

      {

          memset(color,,sizeof(color));

          int mid=(l+r)/;

          Ci=p[mid].z;

          if(pd())

            {

                r=mid-;

                ans=Ci;

          }

        else l=mid+;

      }

    printf("%d\n",ans);

    return ;

}

/*

并茶几版本

因为就有两个监狱 两个人要么一个监狱 要么不一个监狱（废话- - ）

为了使ans最小 我们一定会让ci大的组合先分开

所以按ci排一遍序 然后for每一对

如果发现他俩在一个集合 输出ci结束

否则的话 我们希望的是把他两个分开

即把他们分别跟对方的仇人合并

所以我们假设每个人的仇人都是i+n

对于i 如果另外两个人都合并到了i+n 说明两个人一定在一所监狱

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#define maxx 40010

#define maxn 200010

using namespace std;

int fa[maxx],n,m;

struct node

{

    int a;

    int b;

    int c;

}s[maxn];

int cmp(const node &x,const node &y)

{

    return x.c>y.c;

}

int find(int x)

{

    if(x!=fa[x])fa[x]=find(fa[x]);

    return fa[x];

}

int main()

{

    int i,j;

    cin>>n>>m;

    for(i=;i<=n*;i++)fa[i]=i;

    for(i=;i<=m;i++)

      cin>>s[i].a>>s[i].b>>s[i].c;

    sort(s+,s++m,cmp);

    for(i=;i<=m;i++)

      {

          int r1=find(s[i].a);

          int r2=find(s[i].b);

          if(r1==r2)

            {

                cout<<s[i].c;

                return ;

          }

        fa[r1]=find(s[i].b+n);

        fa[r2]=find(s[i].a+n);

      }

    cout<<;

    return ;

}

noip 2010 关押罪犯 （二分图染色 并茶几）的相关教程结束。