题目描述

给定一个无向图，把图中的点分成两组，st同一组内部边的权重的最大值最小。
check(mid)把仇恨值大于mid的罪犯分到两组，如果可以mid则为最优解

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=20010,M=200010;
int h[N],e[M],ne[M],w[M],idx,st[N];
int color[N]; //0表示未染色，1表示白色，2表示黑色
int n,m;

int dfs(int u,int c,int mid)
{
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(w[i]<=mid) 
        {
            continue;
        }
        if(color[j])
        {
            if(color[j]==c) return 0;
        }
        else if(!dfs(j,3-c,mid))
        {
            return 0;
        }
    }
    return 1;

}

int check(int mid)
{
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++)
    {
        //如果未染色
        if(color[i]==0)
        {
            //check返回0就说明染色失败
            if(!dfs(i,1,mid)) 
            {
                return 0;
            }
        }
    }
    return 1;
}

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}


int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        //check返回1说明染色成功，因为mid无限大的时候，全都可以染色成功，但不是最小的
        //此时需要让r左移，mid变小
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r;
    return 0;

}

二刷,又复习了一遍二分图染色

有几处需要注意的地方：
1. 在染色的dfs函数里，必须做到最后才能返回1，其他步骤只能在失败时返回0

#include <iostream>
#include <cstring>

using namespace std;

const int N=20010,M=200010;
int h[N],e[M],ne[M],w[M],idx,st[N];
int color[N]; //0表示未染色，1表示白色，2表示黑色
int n,m;
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int dfs(int u,int c,int mid)
{
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(w[i]<=mid) continue;
        if(!color[j])
        {
            if(!dfs(j,3-c,mid))
            return 0;
        }
        else
        {
            if(color[j]==c) return 0;
        }
    }
    //必须全部做完才能 return 1
    return 1;
}

int check(int mid)
{
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++)
    {
        if(color[i]==0)
        {
            if(!dfs(i,1,mid))
            {
                return 0;
            }
        }
    }
    return 1;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int l=0,r=1e9+1;
    while(l<r)
    {
        int mid=l+r>>1;
        //如果mid成立 ,说明mid可以缩小
        if(check(mid)) r=mid;
        else
        l=mid+1;
    }
    cout<<l;
}

三刷，整体思路是记得的，但是具体细节没实现出来

1. 二分图的实现： 循环内两个失败条件：注意第一个的写法

if(!color[j])
{
    if(!draw(j,3-c,mid))
    return 0;
}
else if(c==color[j]) return 0;

全部做完才能return 1

1. 如果遇到边权<=mid的，可以无视这俩人，因为可以容忍

2. 二分图的判断也忘了，因为图可能是不连通 的，所以必须从第一个点开始遍历，如果这个点没被染色则染色他，所有点都做一遍，这也是两个失败条件中第二个可能发生的原因

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
int n,m;

const int N=20010;
int e[N*10],ne[N*10],st[N],h[N],w[N*10];
int idx;
int color[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int draw(int u,int c,int mid)
{
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        //如果他俩(j和u)的怒气值小于mid，就说明可以容忍，就说明他俩相当于不存在
        //如果mid=正无穷，该函数一定返回1，因此要不断缩小mid
        if(w[i]<=mid) continue;

        if(!color[j])
        {
            if(!draw(j,3-c,mid))
            return 0;
        }

        else if(c==color[j]) return 0;

    }
    return 1;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    int l=0,r=1e9+1;
    while(l<r)
    {
        int mid=l+r>>1;

        int flag=1;
        memset(color,0,sizeof color);
        for(int i=1;i<=n;i++)
        {
            if(!color[i])
            {
                if(!draw(i,1,mid))
                {
                    flag=0;
                    break;
                }
            }
        }
        if(flag)
        {
            r=mid;
        }
        else l=mid+1;
    }
    cout<<l;
    return 0;
}