二分图总结

基础知识

\qquad 假设存在一张图 $G=(V,E)$，如果我们可以将 $V$ 分成两个非空点集 $V_L,V_R$，使得这两个点集内部无边，两个点集之间允许连边，那么我们便称图 $G$ 是一张二分图，将点集 $V_L,V_R$ 分别成为二分图的左部、右部。

二分图判定

\qquad 一个很显然的结论是：如果一张图中存在奇环，那么这张图一定不是二分图；否则一定是二分图。那么我们便可以通过给点染色的方式来判断这张图中是否存在奇环。

\qquad 核心 $Code:$

int dfs(int x) {
	int flag = 0;
	for(int i = head[x]; i; i = edge[i].lst) {
		int v = edge[i].to;
		if(col[v] && col[v] == col[x]) {//相邻点颜色相同，存在奇环
			flag = 1;
			break;
		}
		else if(col[v] && col[v] == 3 - col[x]) continue;
		col[v] = 3 - col[x], flag |= dfs(v);
	}
	return flag;
}

二分图匹配

\qquad 对于一张二分图 $G=(V,E)$，如果我们选取图中的一个边集 $E^{\prime }$，使得 $E^{\prime }$ 中任意两条边无公共端点，那么我们称 $E^{\prime }$ 是该二分图的一组匹配。一张二分图会有许多个匹配。这些匹配中，$|E^{\prime }|$ 最大的一个匹配称为该二分图的一组最大匹配。如果一张二分图的左部点数等于右部点数等于 $N$，且最大匹配的大小也等于 $N$，那么我们称这组最大匹配为该二分图的完备匹配。如果一张二分图中的点可以被匹配多次，但是有一个上界，那么我们称这类问题为二分图的多重匹配问题。如果一张二分图中的边带边权，那么我们定义二分图的所有最大匹配中边权和最大的那组匹配为该二分图的带权最大匹配。

Hungarian 算法

\qquad 对于任意一组匹配 $E^{\prime }$，我们定义 $E^{\prime }$ 中的边为匹配边，匹配边的端点是匹配点，剩余的边和点分别成为非匹配边和非匹配点。如果存在一条路径链接了两个非匹配点，这条路径满足非匹配边和匹配边交替出现，那么我们称这条路径为一条增广路，或交错路。

\qquad 很显然，一条增广路的长度一定是奇数，而且如果我们把这条路径上所有边的状态取反，即非匹配边变为匹配边，匹配边变为非匹配边，那么取反后在原图中便可得到一个更大的匹配。匈牙利算法（Hungarian）便是依靠这一性质展开的。它的主要流程是：1、在原图中寻找增广路；2、对增广路的所有边状态取反；3、重复上述过程直至不存在增广路。

\qquad 整个过程最主要的一部便是找增广路。Hungarian 算法的实现方法是：对于每个左部点 $x$，枚举它的所有出边所连的右部点 $y$，如果枚举到点 $y$ 当前是非匹配点，那么他们之间就构成了一条长度为 $1$ 的增广路，匹配即可；如果枚举到点 $y$ 已经与点 $x^{\prime }$ 匹配，但从 $x^{\prime }$ 出发还可以找到一个 $y^{\prime }$ 与 $x^{\prime }$ 匹配，那么 $x?y?x^{\prime }?y^{\prime }$ 便构成了一条增广路，匹配即可。Hungarian 算法采取 $dfs$ 的实现方式，这样在递归回溯时便可直接对路径状态进行取反。时间复杂度 $O(nm)$。

\qquad 核心 $Code:$

bool match(int x) {
	for(int i = head[x]; i; i = edge[i].lst) {
		int v = edge[i].to;
		if(!vis[v]) {
			vis[v] = 1;
			if(!p[v]/*还未匹配*/ || match(p[v])/*已匹配，但p[v]还可以找到新的匹配*/) {
				p[v] = x;//匹配
				return 1;
			}
		}
	}
	return 0;//无法匹配
}

int Hungarian() {
	int ans = 0;
	for(auto i : M) {//枚举左部点，M中存的是左部点
		memset(vis, 0, sizeof vis);
		if(match(i)) ans ++;//匹配成功
	}
	return ans;
}

KM 算法

\qquad KM 算法主要用于解决二分图的带权最大匹配。但是它只能在满足带权最大匹配一定是完备匹配的图中正确求解。

\qquad 在 Hungarian 算法中，如果某个左部点匹配失败，那么在 $dfs$ 的过程中，所有访问过的节点和边共同构成一棵树。这棵树的根节点和叶子节点都是非匹配点，而且这棵树的奇数层上的边一定是非匹配边，偶数层上的边一定是匹配边。我们称这样一颗树为交错树。

\qquad 在二分图中，我们给每个左部节点赋值 $A_i$，给每个右部节点赋值 $B_j$，这些值要满足 $?i,j,A_i+B_j\ge w(i,j)$，$w(i,j)$ 是 $i,j$ 之间的边权，没有边视作负无穷。我们把这些值称为顶点标记值，简称顶标。

\qquad 我们把二分图中所有节点和满足 $A_i+B_j=w(i,j)$ 的边构成的子图称为该二分图的相等子图。

\qquad 基于相等子图的概念，我们可以得到一个定理：若相等子图中存在完备匹配，那么这个完备匹配就是二分图的带权最大匹配。证明也很简单：相等子图中完备匹配的边权值和等于 ${\sum }_{i=1}^n{A}_i+B_i$，即所有顶标之和。又因为 $?i,j,A_i+B_j\ge w(i,j)$，所以一定不存在大于这一权值的匹配。

\qquad KM 算法的原理便是这一定理。它的流程是：1、先给所有点在满足顶标的要求的基础之上任意赋一个顶标；2、适当调整顶标使得扩大相等子图规模，直至相等子图中存在完备匹配。

\qquad 对于当前的相等子图，我们用 Hungarian 跑最大匹配。如果最大匹配不是完备匹配，那么必然有一个点没有匹配，这个点在 $dfs$ 时形成了一棵交错树。现在我们要想扩大相等子图的规模，就要从两个角度考虑：1、让右部点访问到更多左部点；2、让左部点访问到更多右部点。因为在 Hungarian 的过程中，我们并不会改变已有的匹配，所以右部点是无法访问到更多的左部点的（因为交错树上右部点访问左部点必须走匹配边）。我们只能考虑如何让左部点访问到更多右部点。

\qquad 我们现在构造一组方案：让交错树中的左部节点的顶标都减小 $\delta$，右部节点的顶标都增加 $\delta$。现在，我们来分析这一构造产生的影响。

\qquad 对于一条匹配边，它的两端点要么同时在交错树上，要么同时不在交错树上，两端点顶标和不变，所以不会受影响；对于一条非匹配边，除了出现上述两种情况外还可能出现：左部点在交错树上，右部点不在交错树上。此时，两端点顶标和就会减小。减小过后，这条边就有可能被加入到相等子图中，被访问到。所以，这样的构造是可以扩大相等子图的规模的。但是，为了保证 $A_i+B_j\ge w(i,j)$ 的性质不被破坏，$\delta$ 的取值应该是 $\min (A_i+B_j?w(i,j))$。这样不断重复下去，直到所有左部点都匹配成功，此时我们便得到了原图的带权最大匹配。

\qquad 但是，上述过程是可以进一步优化的。因为每次修改顶标后，相等子图的规模只会扩大，不会减小，所以我们每次遍历时只需从最新加入的边开始即可。不过此时如果匹配成功，我们是无法直接通过递归回溯来更新增广路的，因为我们并没有从根开始遍历。所以，我们需要记录一个 $lst$ 数组表示每一个右部点在交错树上的上一个右部点，按照 $lst$ 倒退回去即可更新增广路。时间复杂度 $O(n^3)$。

\qquad 核心 $Code:$

/*
va[i]:左部点i是否在交错树上
vb[i]:右部点i是否在交错树上
la[i],lb[i]:左部点、右部点顶标
p[i]：右部点i匹配的左部点
lst[i]:如上文
upd[i]:右部点i对应的最小的delta
*/
bool dfs(int x, int fa) {
	va[x] = 1;
	for(int i = 1; i <= n; i ++) {
		if(!vb[i]) {
			if(la[x] + lb[i] == w[x][i]) {//在相等子图上
				vb[i] = 1, lst[i] = fa;
				if(!p[i] || dfs(p[i], i)) {
					p[i] = x;
					return 1;
				}
			}
			else if(upd[i] > la[x] + lb[i] - w[x][i]) {//不在
				upd[i] = la[x] + lb[i] - w[x][i];
				lst[i] = fa;//注意！！！此时右部点i可能作为倒推的起点，所以需要记录lst值
			}
		}
	}
	return 0;
}

int KM() {
	for(int i = 1; i <= n; i ++) {
		lb[i] = 0, la[i] = -0x7f7f7f7f;
		for(int j = 1; j <= n; j ++) la[i] = max(la[i], w[i][j]);
	}
	memset(p, 0, sizeof p);
	for(int i = 1; i <= n; i ++) {
		memset(va, 0, sizeof va), memset(vb, 0, sizeof vb);
		memset(upd, 0x7f, sizeof upd), memset(lst, 0, sizeof lst);
		int st = 0; p[st] = i;//一开始让左部点i和右部点0匹配
		while(p[st]) {
			if(dfs(p[st], st)) break;//匹配成功
			int delta = 0x7f7f7f7f;
			for(int j = 1; j <= n; j ++) {
				if(!vb[j] && delta > upd[j]) delta = upd[j], st = j;//从最新加入的边开始，所以st要一起更新
			}
			for(int j = 1; j <= n; j ++) {
				if(va[j]) la[j] -= delta;
				if(vb[j]) lb[j] += delta;
				else upd[j] -= delta;
			}
			vb[st] = 1;
		}
		while(st) p[st] = p[lst[st]], st = lst[st];//倒推更新增广路
	}
	//此时p中便是右部点的匹配方案
}

\qquad 例题：Ants。

二分图覆盖与独立集

\qquad 给定一张二分图 $G=(V,E)$，从中选出一个点集 $V^{\prime }$，如果 $E$ 中任意一条边都有至少一个端点在 $V^{\prime }$ 内，那么我们称点集 $V^{\prime }$ 为 $G$ 的一个点覆盖集。如果 $V^{\prime }$ 中的点两两之间无边，那么我们称 $V^{\prime }$ 为 $G$ 的一个点独立集。

二分图最小点覆盖

\qquad 二分图中 $|V^{\prime }|$ 最小的一个点覆盖集就被称为该图的最小点覆盖。在这里，有一个定理（柯尼希定理）：二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。证明不会……

\qquad 例题：[USACO05JAN] Muddy Fields G，Machine Schedule。

二分图最大独立集

\qquad 二分图中 $|V^{\prime }|$ 最大的一个点独立集就被称为改图的最大独立集。在这里，有一个定理：最大独立集的大小等于 $n$ 减去最大匹配数。证明不会……

DAG 的最小路径点覆盖

\qquad 给定一张 DAG，要求用尽量少的不相交的边覆盖 DAG 中的所有点，这一问题被称作 DAG 的最小路径点覆盖问题。在这里，有一个定理：DAG 的最小路径点覆盖中包含的路径数等于 $n$ 减去它的拆点二分图（把 $1～n$ 拆成 $1～2n$，其中 $1～n$ 为左部点，$n+1～2n$ 为右部点，对于原图中的每一条边 $(x,y)$，在新图上对应边 $(x,y+n)$，最终得到的二分图被称为拆点二分图）的最大匹配数。证明依旧不会……

\qquad 例题：Air Raid。

DAG 的最小路径可重复点覆盖

\qquad 如果一个点可以被覆盖多次（即选的边允许相交），那么该怎么办呢？

\qquad 如果两条路径 $x_1～p～y_1$ 和 $x_2～p～y_2$ 相交于点 $p$，那我们完全可以把它看成 $x_1～y_1$，$x_2～y_2$ 这样的两条不相交路径，所以我们可以先对原图传递闭包，然后再做一般的最小路径覆盖问题。