算法分析

怨气值数据范围是1~10^9，暗示着我们用二分，为了让监狱内部的怨气值越小，则需要尽量把怨气值大的罪犯分开

• check(x)：表示将任意怨气值大于x的两名罪犯放在两个监狱，且两个监狱内部的最大怨气值均不超过x，符合返回true，符合返回false

• check(x)函数的实现，验证该图中是否为一个二分图，即监狱内部怨气值小于x的边均去掉，用染色法验证

注意：两个罪犯的怨气值最小的情况下是1，若监狱内部发生冲突事件怨气值的最大值一定大于等于1，而本年内监狱中未发生任何冲突事件，输出是0，因此二分的初始范围是l = 0，r = 10^9,

时间复杂度 $O(logC(n + m))$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int n,m;
    static int N = 20010;
    static int M = 200010;
    static int[] h = new int[N];
    static int[] w = new int[M];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int[] color = new int[N]; //0 - 未染，1 - 黑色，2 - 白色
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static boolean check(int x)
    {
        Arrays.fill(color,0);//初始化未染色
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i = 1;i <= n;i ++)
        {
            if(color[i] == 0)
            {
                color[i] = 1;
                q.add(i);
                while(!q.isEmpty())
                {
                    int t = q.poll();
                    for(int j = h[t];j != -1;j = ne[j])
                    {
                        if(w[j] <= x) continue;//若怨气值小于mid则不连边
                        int k = e[j];
                        if(color[k] == 0)
                        {
                            color[k] = 3 - color[t];
                            q.add(k);
                        }
                        else if(color[k] == color[t]) return false;
                    }
                }
            }
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a,b,c);
            add(b,a,c);
        }
        int l = 0,r = 1000000000;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        System.out.println(l);
    }
}