二分图相关

little-corn / 2024-07-17 / 原文

% $\rm \color{red}{L}\color{black}{BY}$ 学长。

零、定义：

二分图:

二分图是一张图 $G = (V, E)$，其中点集 $V$ 可以分成两个部分 $(V1, V2)$，满足 $V1 \cap V2 = \emptyset, V1 \cup V2 = V$，且 $V1, V2$ 中均没有边，即对于 $\forall e \in E, e = (v_i, v_j)$，均有 $v_i \in V1, v_j \in V2$。注意：接下来称 $V1$ 为左部点，$V2$ 为右部点。

匹配：

一张图的匹配定义为一个原图的一个子图，且满足任意两条边均没有公共端点。一个匹配的大小定义为其中边的个数，一个图的最大匹配定义为匹配的大小最大的一个匹配。特殊的，对于一个匹配且该匹配完全包含左部点或右部点时，我们称该匹配是完美匹配，完美匹配一定是原图中的最大匹配。

点覆盖：

一张图的覆盖定义为原图中点集的一个子集，满足原图中每条边均有一个端点在该点集中。一个覆盖的大小定义为点集的大小，最小点覆盖就是原图中最小的覆盖。

独立集：

一张图的独立集定义为原图中点集的一个子集，满足原图中每条边的端点至少有一个不在该点集中。一个覆盖的大小定义为点集的大小，最大独立集就是原图中最大的独立集。

一、二分图最大匹配：

二分图中的最大匹配求法较一般图是简单的，我们接下来探究对于二分图如何求最大匹配。

我们要引入匈牙利算法。依次考虑左部点并进行匹配，假设我们考虑到第 $i$ 个点。我们找到与之相连的且没有标记过的右部点 $v$，并做标记，若 $v$ 没有匹配，则给让 $v$ 跟 $i$ 匹配并返回 $i$ 匹配成功。否则我们考虑更换与 $v$ 匹配的左部点的匹配点，若更换成功，则将 $v$ 与 $i$ 匹配，否则考虑下一个点。当 $i$ 一个点都没有匹配到时，返回没有找到即可。

注：其中我们称该过程中走的边为增广路或交替路，因为这条路径上的边是匹配边和非匹配边交替的。

匈牙利算法看起来相当暴力，实际上，它的时间复杂度为 $O(n^3)$。

code

bool dfs(int u){
	for(int i = 1; i <= n; i++){
		if(!vis[i] && G[u][i]){
			vis[i] = true;
			if(!match[i] || dfs(match[i])){
				match[i] = u;
				return true;
			}
		}
	}
	return false;
}

二、二分图最小点覆盖：

对于求解二分图中的最小点覆盖问题，我们可以考虑将其转化为最大匹配问题求解。

König定理：二分图中，最大匹配等于最小点覆盖。

证明：

首先我们可以知道最大匹配 $\le$ 最小点覆盖。因为最小点覆盖至少要覆盖到匹配边，而匹配边端点互不相交，故每条匹配边都需要一个单独的点去覆盖。

接下来我们考虑构造出一种方案取到下界。具体方案是从未匹配的右部点出发，走交替路并且标记经过的点，最后选择左边标记的点和右边未标记的点。画图容易发现每个点恰好是一条匹配边的端点，原因大概是从左向右走的一定是匹配边，因此左边标记过的点如果是匹配点，一定会将所在匹配边的右部点标记而不会选进点集中。而右边未标记的点一定是匹配点，于是恰好覆盖了所有匹配边且恰好没有重复。

对于完全覆盖的证明，我们考虑使用反证法，假设有一条边没有被覆盖到，则它对应的左部点一定是未标记过，而右部点是标记过的。进一步的，该边不可能是未匹配边，但是若该边是匹配边，则右部点只可能是由左部点走过来，但是这样左部点就标记了，推出矛盾，从而定理得证。

三、二分图最大独立集：

与最小点覆盖问题类似，我们依旧考虑转化问题。

实际上，我们可以考虑将点覆盖与独立集建立映射关系。具体的，一个独立集的补集即为原图的一个点覆盖。这是因为独立集中的点两两之间没有任何边，于是剩下的点就会覆盖所有边。

从而最大独立集大小 = 点数 - 最小点覆盖。

四、Hall 定理：

Hall 定理是关于二分图完美匹配的强定理，适用于判定的情况。

Hall 定理： 对于一个二分图，存在完美匹配的充分必要条件是对于任意点集 $S \in V1, S \cap V2 = \emptyset$，它的邻域 $N(S)$ 满足 $|N(S)| \ge |S|$。

证明：

必要性是显然的，这里证明充分性。

还是考虑使用反证法，设这个图找完最大匹配后还有至少一个未匹配点 $a$。找到与 $a$ 相邻的一个点 $b$，讨论 $b$ 的匹配情况：

若 $b$ 是非匹配点，可以匹配使得匹配数加一，矛盾。
若 $b$ 是匹配点，则一定会有一个点匹配点 $c$ 与 $b$ 相连。

由题设，一定还会有一个点 $d$ 和 $a$ 或 $c$ 相连（因为 $|N({a, c})| \ge 2$）。那么我们再对点 $d$ 进行讨论：

若 $d$ 是非匹配点，可以匹配使得匹配数加一，矛盾。
若 $d$ 是匹配点，则一定会有一个点匹配点 $e$ 与 $d$ 相连。

同理会有一个点 $f$ 与 $a$ 或 $c$ 或 $e$ 相连.......这样会一直循环下去，但由于点的有限性，而且由于现在的匹配不是完美匹配，最终一定会找到一个未匹配点，结果会得到一个增广路，于是得到矛盾，证毕。

五、例题：

1.CF981F Round Marriage

看到最小化最大值，考虑二分答案 $P$。

我们将距离小于等于 $P$ 的男女连上边，问题转化为该二分图是否存在完美匹配。若我们将 $a, b$ 从小到大排序并断环为链，容易发现 $a_i$ 与 $b$ 数组有连边的点是一个区间。我们欲找到一个 $a$ 中集合不满足 $\rm Hall$ 定理，即尽量男女数量的差 $ < 0$。这里有一个关键的性质：使得男女数量差 $< 0$ 的选择集合在 $a$ 中至少有一个是一个连续的区间。

考虑反证法证明。若不存在一个连续的区间且满足差 $<0$，则至少有两个相离的区间满足，其中至少有一个差 $< 0$，这个区间就是符合题设的。

设对于 $a_i$，他在 $b$ 中有连边的区间是 $[L_i, R_i]$。对于一个区间 $(i, j]$ 若它不满足 $\rm Hall$ 定理，则 $j - i \ge R_j - L_i$，移项得 $L_i - i \ge R_j - j$，维护 $1 ~ i - 1$ 的 $R_j - j$，并判断即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
const int N = 1e6 + 10, INF = 1e18;
 
int n, L, a[N], b[N];
 
bool check(int d){
	int mn = INF;
	for(int i = n + 1; i <= 3 * n; i++){
		int L = lower_bound(b + 1, b + 4 * n + 1, a[i] - d) - b, R = upper_bound(b + 1, b + 4 * n + 1, a[i] + d) - b - 1;
//		if(R - L >= n) L = R - n + 1;
//		cout << i << " " << d << " " << L << " " << R << "\n";
		if(i - R > mn) return false;
		mn = min(mn, i - L);
	}
	return true;
}
 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> L;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);
	for(int i = n + 1; i <= 4 * n; i++) b[i] = b[i - n] + L, a[i] = a[i - n] + L;
	int l = 0, r = L, ans = 0;
	while(l <= r){
		int mid = (l + r >> 1);
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << ans;
	
	return 0;
}

2.P3488 [POI2009] LYZ-Ice Skates

将鞋子拆成 $k$ 个点并与人连边，于是再次转化为了判断完美匹配问题。与上一题类似的，能够卡掉完美匹配的其中肯定是有一个区间的。设第 $i$ 号脚的人有 $a_i$ 个，则区间 $[i, j]$ 不满足 $\rm Hall$ 定理的判定条件是 $\sum^r_{i = l}{a_i} \ge (r - l + 1) * k + d * k$，移项得：$\sum^r_{i = l}{a_i - k} \ge k * d$。这等价与将所有 $a_i$ 全体减 $k$ 后求最大子段和，支持单点修改。线段树即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;

int n, m, k, d;

namespace Segtree{
	#define ls (o << 1)
	#define rs (o << 1 | 1)
	#define mid (l + r >> 1)
	struct node{
		int pre, suf, sum, mxsum;
	}tnode[N << 2];
	node merge(struct node n1, struct node n2){
		node ret; ret.sum = n1.sum + n2.sum;
		ret.pre = max(n1.pre, n1.sum + n2.pre);
		ret.suf = max(n2.suf, n2.sum + n1.suf);
		ret.mxsum = max(max(n1.mxsum, n2.mxsum), n1.suf + n2.pre);
		return ret;
	}
	void pushup(int o){tnode[o] = merge(tnode[ls], tnode[rs]);}
	void build(int o, int l, int r){
		if(l == r){tnode[o] = {-k, -k, -k, -k}; return;}
		build(ls, l, mid); build(rs, mid + 1, r);
		pushup(o);
	}
	void add(int o, int l, int r, int x, int t){
		if(l == r){int v = tnode[o].mxsum + t; tnode[o] = {v, v, v, v}; return;}
		if(x <= mid) add(ls, l, mid, x, t);
		else add(rs, mid + 1, r, x, t);
		pushup(o);
	}
}
using namespace Segtree;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k >> d; build(1, 1, n);
	while(m--){
		int r, x; cin >> r >> x;
		add(1, 1, n, r, x);
		if(tnode[1].mxsum > d * k) cout << "NIE" << "\n";
		else cout << "TAK" << "\n";
	}

	return 0;
}