257. 关押罪犯 - AcWing题库 【细节二分 | 细节二分图】

257. 关押罪犯 - AcWing题库

这个地方的逻辑错误：

记住vis的作用，是为了防止多次访问同一个点，减少时间复杂度用的。

这个题是允许同一个点被“访问多次”的，访问到了的时候，还需要判断后再返回。

bool erfentu(int limits, int u, int color_now)
{
    vis[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(w[i] <= limits) continue;
        if(vis[j] && (color_now != color[j])) return false;
        color[j] = color_now;
        return erfentu(limits, j, color_now ^ 1); 
    }
    return true;
}

w[i]<=limits(mid)，取等，也就说把所有的大于limits的都连线。

对于所有大于limits的我们不容忍他们在一个监狱。

剩下的小于等于的都是可以成立的，对应我们可以容忍小于等于limits在一个监狱。也就是当mid = w[i]时，是成立的，所以要取等。

可以发现，对于这个题，当二分的mid是无限大的时候一定满足条件。那么我们就轻而易举的知道这是个最大值最小问题。

如果说k是容忍度limits的最小值即答案，可知当limits小于k的时候，条件变得非常苛刻，我们无法做到所有的满足w[i] > limits对应的a和b都在不同的监狱。

或者说，当limits（容忍度） > k时，我们总是可以更容易地能去分配这些人，因为我们的条件没有那么的苛刻，如果我们的容忍度无限大，那随便放都可以完成任务。

代码的1个细节：

如果用异或1，^1的话，color要初始化为-1，判断也要是！= -1。
或者0初始化，1和2判断

#include
typedef long long ll;
using namespace std;
const int N = 2e4 + 10;
const int M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
int color[N];
bool erfentu(int limits, int u, int color_now)
{
    color[u] = color_now;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(w[i] <= limits) continue;
        if(color[j] == -1)
        {
            if(!erfentu(limits, j, color_now ^ 1))
                return false;
        } else if(color[j] == color_now)return false; 
    }
    return true;
}
 
bool check(int mid)
{
    memset(color, -1, sizeof color);
    for (int i = 1; i <= n; i ++ ) {
        if(color[i] == -1 && !erfentu(mid, i, 1))
         return false;
    }
    return true;
}
 
int main(){
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);         
    }
 
    int l = 0, r = 1e9 + 10;
    while(l < r)
    {
        int mid = l + r >> 1;
        //cout << l << ' ' << r << ' ' << mid << '\n';
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
 
    return 0;
}