二分图的定义与判定

定义

对于一张有 \(n\) 个节点的无向图（\(n \ge 2\)），可以分成两个集合 \(A\) 与 \(B\) 两个非空集合，满足 \(A \cap B = \varnothing\)，且任意一个集合内的点之间都没有边相连。那么称这张图为二分图。

判定

不加证明地给出一个定理：

一张无向图是二分图，当且仅当图中不存在奇环。

根据这个定理，可以用染色的方法进行二分图判定。用黑白二色标记图中节点，当一个节点被交际后，将所有与它直接相连的点标记为与它相反的颜色。那么对于一个点 \(x\)，颜色为 \(col_x\)，存在与它直接相连且已经被染色的点 \(y\)，满足 \(col_x = col_y\)，那么说明图中存在奇环。

复杂度 \(O(n+m)\)，其中 \(n\) 为点数，\(m\) 为边数。

bool dfs(int x,int color) {
	v[x]=color;
	for(int i=h[x];i;i=e[i].nxt) {
		int y=e[i].to;
		if(v[y]==color) return 0;
		if(!v[y]&&!dfs(y,3-color)) return 0;
	}
	return 1;
}

二分图最大匹配

如果一个边集满足「任意两条边都没有公共端点」，那么这个边集称为该图的一组匹配。在二分图中，包含边数最多的一组匹配称为二分图的最大匹配。

对于一组匹配 \(S\)，属于 \(S\) 的边称为“匹配边”，不属于它的边称为“非匹配边”。匹配边的端点称为“匹配点”，其他节点称为“非匹配点”。

在二分图中，如果存在链接两个非匹配点的路径 \(p\)，且非匹配边与匹配边在 \(p\) 上交替出现，那么 \(p\) 就是 \(S\) 的增广路。

它必然有以下性质：

• 长度 \(l\) 为奇数。否则连接某一个端点的增广路上的边是匹配边，与它是非匹配点相矛盾。
• 路径上第 \(1,3,5,\cdots l\) 条边是非匹配边，\(2,4,6,\cdots l-1\) 条边为匹配边。由定义不难得出。

由于这两条性质，得出在增广路上，匹配边的数量必定是非匹配边的数量 -1，那么如果将路径上所有的边的状态取反，那么就能减少一条增广路，得到一个新的匹配 \(S'\)，其中匹配边的数量为 \(S\) 中匹配边的数量 +1。进而得到推论：

二分图的一组匹配 \(S\) 为最大匹配，当且仅当图中不存在 \(S\) 的增广路

匈牙利算法

又称为增广路算法，用于计算二分图最大匹配，其过程为：

1. 设 \(S = \varnothing\)，即图中所有边都是非匹配边。
2. 寻找增广路 \(p\)，并且所有状态取反，得到更大的匹配 \(S'\)。
3. 重复第 2 步，直到图中不存在增广路，此时得到的 \(S''\) 即为改二分图的最大匹配。

这个算法的核心为寻找增广路。

称 \(x\) 与 \(y\) 匹配当且仅当 \((x \rightarrow y)\) 在匹配 \(S\) 之内。匈牙利算法依次尝试给每一个左部节点 \(x\) 寻找一个匹配的右部节点 \(y\)。\(x\) 与 \(y\) 能够匹配，需要满足以下条件之一。

1. \(y\) 本身是非匹配点。那么 \((x \rightarrow y)\) 就是一条非匹配边，构成长度为 1 的增广路。

2. \(y\) 已经与左部节点 \(x'\) 匹配，但是从 \(x'\) 出发能够找到一个右部节点 \(y'\) 与它匹配。此时 \(x \rightarrow y \rightarrow x' \rightarrow y'\) 是一条增广路。

找到增广路之后直接回溯，将路径上的匹配状态取反， \(S\) 中边的个数就 +1。

这个算法的正确性基于：当一个节点成为匹配点后，至多因为找到新的增广路而更换匹配对象，但不会变为非匹配边。

复杂度 \(O(n^2)\)。

bool dfs(int x) {
	for(int i=h[x];i;i=e[i].nxt) {
		int y=e[i].to;
		if(!v[y]) {
			v[y]=1;
			if(!match[y]||dfs(match[y])) { match[y]=x; return 1; }
		}
	}
	return 0;
}
signed main() {
	for(int i=1;i<=n;++i) {
		memset(v,0,sizeof(v));
		if(dfs(i)) ++ans;
	}
}
// ans即为最大匹配

二分图多重匹配

二分图，\(N\) 个左部点，\(M\) 个右部点，从中选出尽可能多的边，使得第 \(i\) 个左部节点至多与 \(kl_i\) 条选出的边相连，第 \(j\) 个右部点最多与 \(kr_j\) 条选出的边相连。称之为二分图的多重匹配。

有 4 中解决方案。

1. 拆点。把第 \(i\) 个左部点拆成 \(kl_i\) 个点，把第 \(j\) 个右部点拆成 \(kr_j\) 个右部点。对于原图中的边 \((i,j)\)，在 \(i\) 与 \(j\) 拆成的节点之间分别连边。然后跑最大匹配。
2. 如果所有的 \(kl\) 都为 1 或者所有的 \(kr\) 都为 1，那么只有一侧是多重的。假如左侧是多重的，方法是在匈牙利算法让每个\(i\) 执行 \(kl_i\) 次 DFS。
3. 在上一种方案中，左右两侧是可以交换的。设右侧为多重，那么让每个右部节点 \(i\) 可以匹配 \(kr_i\) 次，超过匹配次数后，依次递归每个匹配的左部点。
4. 网络流。

二分图带权匹配 & KM 算法

对一张带权的二分图求最大匹配，称为二分图带权最大匹配。注意前提是匹配数最大，再最大化边权和。

想了好久，找到了相对比较好理解的讲解方法。

先引入几个概念。

完备匹配

给定一张二分图，其左右节点数均为 \(n\)。如果改二分图最大匹配含有 \(n\) 条边，那么该二分图具有完备匹配。也就是从每个节点出发寻找匹配都能成功。

顶标

在二分图中，给左部节点 \(i\) 一个权值 \(A_i\)，右部节点 \(j\) 一个权值 \(B_j\)。满足 \(A_i + B_j \ge w(i,j)\)，其中 \(w(i,j)\) 为两点之间的边权。这样的 \(A_i\) 与 \(B_j\) 成为顶标。

相等子图

二分图中所有节点与满足 \(A_i + B_j = w(i,j)\) 的边 \((i,j)\) 构成的子图叫做这张二分图的相等子图。

若相等子图中存在完备匹配，则这个完备匹配就是二分图的带权最大匹配。

证明：

在相等子图中，完备匹配的边权和为 \(\sum_{i=1}^n (A_i + B_i)\)，也就是顶标之和。

因为 \(A_i + B_j \ge w(i,j)\)，所以在二分图中，任何一组匹配的边权和都不大于顶标之和。

交错树（匈牙利树）

在匈牙利算法的过程中，如果从某个左部结点出发寻找匹配失败，那么在 DFS 的过程中，访问过的节点和边构成一棵树，满足根为一个左部节点，叶子均为左部节点，且奇数层的边均为非匹配边，偶数层的边均为匹配边。这样的树称为交错树。

一个没用的推论，交错树高度为奇数。

匈牙利算法中的dfs(i)=1就代表不存在以 \(i\) 为根的交错树。

很多地方没有提到的一点就是，如果有交错树，那么必然没有完备匹配，否则与每个从节点出发都能找到匹配相矛盾。这也是下文一系列操作的基础——修改标顶使得尽可能多的边进入相等子图。

知道大概就行了，深入讲真的不太好理解，可能更加学术一点？总而言之，我们的相等子图中不能存在交错树，否则就没有完备匹配，就没有带权最大匹配了！

 

流程

对于 \(i\)，可以把 \(B_i\) 设置为 0，\(A_i\) 设置为 \(\max_{(i \rightarrow j)}{\{ w(i,j) \}}\)，这样一定满足条件。

调整顶标是为了让更多的边 \((i,j)\) 满足 \(A_i + B_j = w(i,j)\)，也就是扩大相等子图。

设当前节点为 \(k\) 且满足在相等子图中存在以它为根的交错树。找到 \((i,j)\)，满足 \(i\) 在以 \(k\) 为根的交错树中但是 \(j\) 不在，那么如果把 \((i,j)\) 加入相等子图，就能够消去这棵交错树了。

如果把这棵交错树中所有左部节点的顶标都减去一个 \(\Delta\)，右部节点都加上一个 \(\Delta\)，那么对于相等子图中一左一右两个节点 \((u,v)\)，\(A_u + B_v\) 和不变，仍然在相等子图中。而 \(A_i + B_j\) 变小了，因为 \(j\) 不在交错树中。

怎么样保证 \((i,j)\) 一定进入相等子图呢？这要求 \(A_i + B_j = w(i,j)\)。找到交错树中的任意节点 \(i\)，令 \(\Delta=A_i+B_j-w(i,j)\)，那么就相当于 \[ A_i - (A_i + B_j - w(i,j)) + B_j = w(i,j) \]

这个显然是成立的。至于 \(i\) 是啥我们不关心，只要这样做就能让 \((i,j)\) 加入相等子图。如果减去太多导致某两个点的顶标和小于边权和了怎么办呢？对于 \(j \in [1,n]\)，取 \(A_i + B_j - w(i,j)\) 的最小值。这个可以在匈牙利算法的过程中预处理出来，记为 \(slack(j)\)。

最终只要把边权和加起来就是答案了。

这么一来最优情况下复杂度是 \(O(n^3)\)，但是很容易就会被卡到 \(O(n^4)\)。使用 BFS 优化匈牙利算法可以做到 \(O(n^3)\)，有时间再写。

KM 算法代码较简单，且在稠密图上表现较好，但是只适用于“原图一定存在完备匹配”的情况。至于费用流的算法，以后再说咯~

bool dfs(int x) {
	va[x]=1;
	for(int y=1;y<=n;++y) if(!vb[y]) {
		if(la[x]+lb[y]==w[x][y]) {
            // la[x]+lb[y]=w[x][y]，(x,y)在相等子图中
            // vb[y]=1表示如果村子交错树，那么y必定在其中
			vb[y]=1;
			if(!match[y]||dfs(match[y])) {
				match[y]=x; return 1;
			}
		} else slack[y]=min(slack[y],la[x]+lb[y]-w[x][y]);
        // 不在相等子图中就更新slack
	}
	return 0;
}
int KM() {
	for(int i=1;i<=n;++i) {
		la[i]=-inf, lb[i]=0;
		match[i]=0;
		for(int j=1;j<=n;++j) la[i]=max(la[i],w[i][j]);
	}
	for(int i=1;i<=n;++i) while(1) {
		for(int j=1;j<=n;++j) v[a]=v[b]=0, slack[j]=inf;
		if(dfs(i)) break;
        // 这样就没有交错树了
		dlt=inf;
		for(int j=1;j<=n;++j) if(!vb[j]) dlt=min(dlt,slack[j]);
        // 取最小值修改标顶
		for(int j=1;j<=n;++j) {
			if(va[j]) la[j]-=dlt;
			if(vb[j]) lb[j]+=dlt;
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans+=w[match[i]][i];
    // ans+=la[i]+lb[i]
    return ans;
}