P1525 关押罪犯 • CoderXL's Blog

这道题有一个贪心+并查集的做法，但本题解主要探讨基于二分图的做法。并查集会在下周的每日一题 ↗中涉及。

既然题目的要素包含：两座监狱、特定罪犯之间的怨气值，那么很适合用二分图的方式解决。

具体来说，考察每条「怨气」边，在最终的方案里，边连接的两条罪犯要么在同一所监狱，要么在不同的监狱。不妨称前一种边是“激活”的边，意味着它会导致冲突真正发生；对应地称后一种边“失活”。

题目要求最小化所有“激活边”中的最大权值，设该值为 $V$ ，那么所有权值大于 $V$ 的边都必须是“失活边”。

这样，对于任何给定的 $V$ ，「判断是否存在合法方案使得所有“激活边”中的最大权值为 $V$ 」的问题，就变成了「能否让所有权值大于 $V$ 的边“失活”」，也就是说「所有权值大于 $V$ 的边能否组成一个二分图」。判断二分图的复杂度是 $O(m)$ .

而 $V$ 与「存在合法方案」之间存在单调关系，即随着 $V$ 的升高，一定是先不存在合法方案，后存在合法方案。事实上，大多数「最小化最大值 / 最大化最小值」的问题都具有类似单调性。这启示我们使用二分答案，每次猜测一个 $V$ ，然后验证合法性，并据此调整猜测区间，直到得出 $V$ 的分界点，即最小的使得合法方案存在的 $V_{\min}$ .

判定二分图使用染色法即可。

总复杂度 $O((N+M) \log C)$ ，其中 $N \le 2\times 10^4,\ M\le 10^5,\ C \le 10^9$ .

#include <bits/stdc++.h>

using namespace std;

const int N = 20010, M = 100010;

struct Edge
{
    int to,v,next;
}edge[M<<1];
int head[N],cnt;

void add(int x,int y,int v)
{
	cnt++;
	edge[cnt]={y,v,head[x]};
	head[x]=cnt;
}

int col[N]; // col=color
int n, m;

bool dfs(int x, int c, int v)
{
	col[x] = c;
	int y;
    for(int i=head[x];i;i=edge[i].next)
    {
	    y=edge[i].to;
	    if(edge[i].v<=v)continue;
	    if(col[y]!=0)
	    {
		    if(col[y]==c)return false;
	    }
	    else
	    {
		    if(!dfs(y, 3-c, v))return false;
	    }
    }
    return true;
}

bool check(int v)
{
    memset(col, 0, sizeof(col));
    for(int i=1;i<=n;i++)
    {
        if(col[i]==0)
        {
	        // 未必都连通，每个连通块单独做
            if(!dfs(i,1,v))return false;
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    int max_v = 0;
    for(int i=1;i<=m;i++)
    {
        int x,y,v;
		cin>>x>>y>>v;
        add(x,y,v);
        add(y,x,v);
        max_v=max(max_v,v);
    }

    int l=0, r=max_v;
    while(l<r)
    {
	    int mid=(l+r)>>1;
        if(check(mid))
        {
			r=mid;
        }
        else
        {
			l=mid+1;
        }
    }
    cout<<l;
    return 0;
}

cpp