二分图最大匹配 & 最大流
引入
给出一个小写字母的子集,从这些字母的所有排列中选出 $N$ 个构成集合 $W$。现从中取出一个最大的子集,使得这个子集中的任意两个单词 $x,y$,满足不能通过交换 $x$ 中一对字母得到 $y$。问这个最大子集的大小。
二分图构造
如果 $x$ 可以通过交换一对字母得到 $y$,我们就连一条边 $(x,y)$,最终答案就是构造出的图的最大点独立集。特别的,此题中构造的图必定是二分图。
原因在于每个单词中,一个字母最多出现一次。考虑某个位置 $p$ 的字母 $c$,$c$ 离开 $p$ 必定对应一次 $c$ 回到 $p$,对每个位置这么考虑,最后交换次数必定是偶数。
由于「最大点独立集+最小点覆盖=顶点个数」,「最小点覆盖=最大匹配」,问题转化为求解二分图的最大匹配。可以利用匈牙利算法求解。
匈牙利算法
匈牙利算法核心思想是,不断从图中寻找增广路,每次找到增广路就可以使得匹配加一。
这里的增广路是指,从一个没有匹配的点出发,沿着非匹配边、匹配边、非匹配边……最终经一条非匹配边到达一个非匹配点的路径。
例子
1,2 分别直接和 4,5 匹配,然后 3 尝试和 4 匹配。
然而 4 已经和 1 匹配 $\to$ 1 能否和其他点匹配? $\to $ 1 尝试和 5 匹配 $\to$ 2 能否和其他点匹配?$\to$ 2 和 6 匹配 $\to$ 1 和 5 匹配 $\to$ 4 和 1 匹配。
这个过程中 $1\to4、2\to5、3\to4\to1\to5\to2\to6$ 都是增广路。
(伪)代码描述
match[1...n] = [NULL] //匹配的点 ans = 0 for all u in V path[1...n] = [false] //点是否在这次搜索的增广路上 if augmentation(u) ++ans bool augmentation(u) for all v:(u,v) in E if path[v] == false path[v] = true if match[v] == NULL || augmentation(v) match[u] = v match[v] = u return true return false
复杂度 $O(VE)$。
一些细节
- 如果可能,没有必要对每个点尝试增广,只需要遍历二分图的一个点集即可。
- 标记一个点是否在增广路上,可以使用时间戳。具体来说,每次第 6 行搜索前标记一下这是第几次搜索,检查一个点是否在增广路上,只需要检查这个点的时间戳是否是这次搜索的时间。
最大流
二分图最大匹配还可以转化为最大流问题。
在原二分图的基础上,令原图的边的容量为无穷大,同时令二分图一个点集中的所有点与源点相连,边的容量为 1,另一个点集都与汇点相连,边容量也为1。那么这个网络的最大流等于最大匹配。
每单位流量对应两个点集中的各一个点。由于在原图基础上新构造的边容量为 1,所以其他流量均与这两个点无关,则它们之间的边即匹配中的一个元素。
求解最大流主要两个系列的算法:
- 增广路。(EK、Dinic、ISAP)
- 预流推进。
比赛中 Dinic 较实用。
EK (Edmond-Karp) 算法
不断寻找从源点 BFS,搜索到汇点的仍可以增大流量路径,暴力增广。
但是这样贪心并不一定可以得到最大流。
如图,$S=1,T=6$,若一开始选择 $1\to2\to4\to6$,之后无法增广,但这并不是最优解。
为了解决这个问题,引入反向弧。为每次增广提供一个撤销选项。具体来说,反向弧初始容量为 0,若一条边容量减少一些,就同时向相反方向增加一些容量。感觉上反向弧相当于回溯。
复杂度 $O(VE^2)$。
Dinic 算法
Dinic 算法是 EK 算法的一个改进。相比 EK,Dinic BFS 过程中对原图进行分层,然后依靠 DFS 进行多路增广。
算法描述并不复杂:
while 可以从残量网络建立分层图 使用 BFS 建立分层图 while 分层图中有增广路 增广,更新答案
Dinic 通常还会加入 『当前弧优化』。原理在于,对于某次 BFS 建立的层次图,某条边不会被多次增广。可以记录一个点有哪些边已经增广过了,下次 DFS 增广跳过增广过的边。
蓝书上的板子
#include <vector> #include <cstring> #include <queue> using namespace std; const int maxn = 100 + 10; const int INF = 1000000000; struct Edge { int from, to, cap, flow; }; struct Dinic { int n, m, s, t; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 void ClearAll(int n) { for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void ClearFlow() { for (int i = 0; i < edges.size(); i++) edges[i].flow = 0; } void AddEdge(int from, int to, int cap) { edges.push_back((Edge){from, to, cap, 0}); edges.push_back((Edge){to, from, 0, 0}); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } };
挖坑+推荐,xht37’s blog
Views: 562