二分图与染色
证明:无向图是二分图,等价于图中不存在奇数环,等价于图能被二染色
先证图中不存在奇数环等价于图能被二染色
充分性:假设不存在奇数环,且不能被二染色。若不存在环,则一定能被二染色,现在无法被二染色,则一定存在环。在该环上以任意点为起点开始染色,假设起点染黑色,由于无法被二染色,则最后一条边的起点也是黑色,则整个环的染色序列为 “黑白黑白…黑”,该序列中点的个数为奇数,即该环是奇数环,这与图中不存在奇数环矛盾,因此假设错误,充分性得证
必要性:假设能被二染色,且存在奇数环。对奇数环以任意点为起点开始染色,起点染黑色,由于点的个数为奇数,最终的染色序列一定是 “黑白黑白…黑”,则最后一条边的两个端点颜色相同,这与能被二染色矛盾,因此假设错误,必要性得证
再证能被二染色,则图是二分图。对图染色后,将黑色点放到一个集合,白色点放到另一集合,则所有边都在集合间,集合内没有边,即图是二分图,由此得证
最后证图是二分图,则图中不存在奇数环。假设某个二分图中存在奇数环,对奇数环上的点二分,起点放集合一,下个点放集合二,由于环上点的个数为奇数,最后一条边的两个端点必然在集合一,即无法将环上的边全部分到集合间,因此图不是二分图,这与假设矛盾,由此得证
二分图是特殊的最大流,难点在于问题转化。二分图本身定义在无向图,但部分算法只需要单向边
最大匹配
以下概念仅针对二分图
- 匹配:若边集内任何两边都没有公共点,则这组边是一个匹配
- 最大匹配:边数最多的匹配
- 匹配点:在匹配中的点
- 非匹配点:不在匹配中的点
- 匹配边:在匹配中的边
- 非匹配边:不在匹配中的边
- 增广路径:从左部非匹配点开始,经过非匹配边、匹配边, … , 最终到达右部非匹配点的路径
性质:最大匹配等价于不存在增广路径
求二分图的最大匹配可以用匈牙利算法
最小点覆盖
定义:选出最少的点,使每条边至少有一个端点被选出
此概念适用于任何无向图,但在二分图中有特殊性质:最大匹配数等于最小点覆盖
证明:
- 由于匹配中的边都没有交点,最小点覆盖至少要从每条匹配边中选出一个点,所以最小点覆盖大于等于最大匹配数
- 构造一种覆盖方式,使等号可以取到:求最大匹配,从左部每个非匹配边出发做增广,标记所有经过的点,选左部所有未被标记的点和右部所有被标记的点
- 左部所有非匹配点一定被标记,因为它们是增广起点
- 右部所有非匹配点一定未被标记,否则增广成功,匹配数增加,这与最大匹配矛盾
- 对于匹配边,左右两点要么同时被标记,要么同时不被标记,因为增广路径要么经过这条边,要么不经过
- 则左部所有未被标记的点是左部的匹配点,右部所有被标记的点都是右部的匹配点
- 则所有选出的点必然在匹配边的两边。对于未被标记的匹配边,选左部点,对于被标记的匹配边,选右部点。这样所有匹配边就全部被覆盖,且点数等于匹配边数
- 考察是否覆盖了非匹配边
- (左部非匹配点, 右部匹配点),左部点是增广起点,右部点一定被标记,因此右部点已被选出
- (左部匹配点, 右部非匹配点),由于右部非匹配点一定未被标记,所以左部的匹配点一定未被标记,因此左部点已被选出
- (左部非匹配点, 右部非匹配点) 不存在,否则匹配数加一,与最大矛盾
由此得证
最大独立集与最大团
定义:从图中选出最多的点,使选出的点间没有边
补图:去掉原图的所有边,若两点间没有边就加一条,形成的新图和原图互为补图
最大团:从图中选出最多的点,使选出的任意两点间都有边
关系:原图的最大独立集是补图的最大团
以上概念适用于任何图,但在二分图中有特殊性质:
从图中选出最多的点,使选出的点间没有边的等价操作是:
- 从图中选出最少的点,使剩下的点没有边(将所有边破坏掉)
- 找最小点覆盖
- 找最大匹配
结论:最大独立集 = 总点数 - 最大匹配
最小路径点覆盖
定义:在 DAG 中,用互不相交(点不重复)路径覆盖所有点的最少条数,称为最小路径点覆盖,或最小路径覆盖
拆点:把每个点拆成出点和入点,对于原图的每条边 $(i, j)$,在新图中加无向边 $(i, j^{\prime})$,则新图是二分图
结论:若原图有 $n$ 个点,二分图的最大匹配数为 $m$,则最小路径点覆盖 $= n - m$
证明:
- 考虑原图中的每条路径在新图中的性质
- 原图中要求互不相交,则路径上每个点的出度和入度都是 $1$
- 出度为 $1$ 等价于在新图上,左部的点只存在一条边连向右部
- 入度为 $1$ 等价于在新图上,右部的点只存在一条边连向左部
- 则原图路径上每条边在新图上都是匹配边,则每条路径对应新图的一个匹配
- 原图中每条路径的终点,都等价于新图左侧的非匹配点
- 因此要让路径最少,等价于让左侧非匹配点最少
- 等价于让左侧匹配点最多
- 等价于最大匹配
最小路径重复点覆盖:用路径覆盖所有点的最少条数,允许不同路径有重复点
- 求原图的传递闭包。即若两点间接连通,则让它们直接连通
- 在传递闭包上求最小路径点覆盖
证明:
对于原图的最小路径重复点覆盖中的所有路径,逐条考虑。若后面的路径包含前面路径中的点,则让重复点前后的点直接连边,转化后的路径即是传递闭包上的最小路径点覆盖中的一条。不可能存在一条路径,它上面所有点都在前面的路径出现,否则就可以去掉这条路径,与最小矛盾。因此原问题的每条路径都对应新问题的一条路径
对于任意新图的最小路径点覆盖中的路径,若其中包含一条传递边,则展开为间接路径,转化后的路径对应原图的最小路径重复点覆盖中的一条
由于两个集合中的元素一一对应,由此得证
其它
- 最优匹配,KM 或最小费用流
- 多重匹配,最大流
题意
把罪犯看成点,若两罪犯之间有仇恨则连一条无向边,长度为它们的怨气值,问题等价于将所有点分到两组,使组内边权的最大值最小
分析
最大值最小,一般可二分,考察解区间范围,及其二段性。若任意罪犯间都没有仇恨,则答案是 $0$。若任意罪犯间的怨气值都是 $INF$,则答案是 $INF$。否则,答案在 $[0, INF],\ INF = 10^9$ 之间。假设答案是 $ans$
- 若 $x \in [0, ans)$,则所有边权大于 $x$ 的边不能分到两组,否则答案就不是 $ans$。因此由所有边权大于 $x$ 的边不能构成二分图
- 若 $x \in [ans, INF]$,则所有边权大于 $x$ 的边能分到两组,因此由所有边权大于 $x$ 的边能构成二分图
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e4 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int cl[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 x) {
cl[u] = c;
for (int i = h[u]; i; i = ne[i]) {
int j = e[i];
if (w[i] <= x) continue;
if (!cl[j] && !dfs(j, 3 - c, x) ||
cl[j] == c)
return 0;
}
return 1;
}
bool check(int x) {
memset(cl, 0, sizeof cl);
for (int i = 1; i <= n; i ++)
if (!cl[i] && !dfs(i, 1, x)) return 0;
return 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int a, b, c; m; m --)
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;
}