算法知识点：二分，染色法判断二分图

复杂度：

解题思路：

将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

我们在之间枚举最大边权 ，当 固定之后，剩下的问题就是：

  • 判断能否将所有点分成两组，使得所有权值大于 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 的边构成的新图是否是二分图。

判断二分图可以用染色法，时间复杂度是 ，其中 是点数， 是边数。

为了加速算法，我们来考虑是否可以用二分枚举 ， 假定最终最大边权的最小值是 :

  • 那么当 时，所有边权大于 的边，必然是所有边权大于 的边的子集，因此由此构成的新图也是二分图。
  • 当 时，由于 是新图可以构成二分图的最小值，因此由大于 的边构成的新图一定不是二分图。
  • 所以整个区间具有二段性，可以二分出分界点 的值。

时间复杂度分析

总共二分 次，其中 是边权的最大值，每次二分使用染色法判断二分图，时间复杂度是 ，其中 是点数，是边数。因此总时间复杂度是 。

C++ 代码 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; 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 limit)
{
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        if (w[i] <= limit) continue;
        int j = e[i];
        if (color[j])
        {
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c, limit)) return false;
    }
 
    return true;
}
 
bool check(int limit)
{
    memset(color, 0, sizeof color);
 
    for (int i = 1; i <= n; i++)
        if (color[i] == 0)
            if (!dfs(i, 1, limit))
                return false;
    return true;
}
 
int main()
{
    scanf("%d%d", &n, &m);
 
    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &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;
    }
 
    printf("%d\n", l);
    return 0;
}



另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
使用优惠券免费报名：DCYxdCJ