二分图

AcWing 257. 关押罪犯

题目

https://www.acwing.com/problem/content/259/

思路

二分+染色法判断二分图 将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。原问题变为：将所有点分成两组，使得组内边的权重的最大值最小。 可以在[0,10^9]之间二分枚举最大边权mid,假设最终最大边权的最小值是ans：

• 当 mid∈[ans,10^9]所有边权大于mid的边，必然是所有边权大于ans的边的子集，成立
• 当mid∈[0,ans-1] 由于ans是新图构成二分图的最小值，因此大于mid的边构成的新图不一定是二分图
• 整个区间具有二段性，可以二分出分界点ans的值

代码

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

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

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


bool 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 false;
    return true;
}



int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        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;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}

本题还可以使用并查集来做！