<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
EK算法
把每个任务抽象成边,两种模式抽象成边的两个端点,需求就转化为了“选出最少的节点构成集合S,使得二分图所有边的两个端点都至少有一个在S中”,典型的二分图最小点覆盖问题,证明起来有点麻烦,直接给出结论:最小点覆盖数 = 最大匹配数
接下来把镜头给到这次的主角:Edmons-Karp算法(简称EK算法)
二分图中的每一条边,可以人为规定其方向是从左半到右半,对于左半的每一个节点,用一个公共始端S去连向它们,然后对于右半的每一个节点,让他们全都连上一个公共终端T,最大匹配数就是加上了S,T之后的网络最大流
对于网络流,可以具体化为水管中的水流,每条水管的流动方向和单位时间内的最大流量都是确定的,水流从一个始端流出,汇集到一个终端,单位时间内从始端流入终端的水流量,就相当于网络的最大流
而EK算法就是把整个网络的最大流先拆分为一条条单独路径上的最大流,这些路径上每条边的容量都大于0,并且由始端出发,到达终端,然后把每条单独路径上的最大流累加起来,寻找这些单独路径也被称为“增广”,这些被找到的可行路径被称为“增广路”
寻找增广路的方式是基于BFS的,每次从始端节点开始,寻找后继节点中还未被访问过且对应边容量大于0的节点,记录它的前驱节点(也就是当前节点),如果找到终端节点了,就直接返回true,否则还需要继续搜索,直到循环结束,还没搜索到终端节点,那就返回false
找到增广路之后,我们从终端开始按照之前记录的前驱节点回溯,第一遍回溯时寻找增广路上容量最小的边(短板效应),这个值$mf$就是当前路径上的最大流(当然对于一次性的二分图匹配问题来说,这个最大流一定是1),先累加上去,然后进行第二轮回溯,此时每回溯一条边,都将正向的容量减少mf,反向的容量增加mf,相当于在两个节点之间建造一条反向的水管,用来进行回退,防止还有增广路和可行流被塞住,如果不理解这么做是为什么,那么我将用一张图来展示这么做的重要性:
左边的网络(最大流为10)按此方式增广之后,如果不回退,到了右图中最大流变为了8,累加上增广后得到的1,只有9,出现了错误,增加了回退之后,按照S,1,2,T增广完毕以后,还能继续按照S,2,1,T的顺序增广,一直到容量为5的边正向容量全都变为0(只是一种方式,下图中还有另一种方式),得出最大流为10的结果
其余细节请见注释
时间复杂度
$O(n*m^2)$
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <functional>
#include <cstring>
#include <queue>
using namespace std;
const int N = 220;
int n, m, k, a, b;
int val[N][N], vis[N], pre[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (true) {
cin >> n >> m >> k;
int source = 0, terminal = n + m + 1;
if (n == 0) break;
memset(val, 0, sizeof(val));
for (int i = 0; i < k; i++) {
cin >> b >> a >> b;
//刚开始就是0模式,所以0不用处理
if (a == 0 || b == 0) continue;
val[a][b + n] = 1;
}
//建立公共始端和终端
for (int i = 1; i < n; i++) val[source][i] = 1;
for (int i = 1; i < m; i++) val[n + i][terminal] = 1;
//寻找增广路
auto findPath = [=](int source, int terminal)->bool {
memset(vis, 0, sizeof(vis));
memset(pre, -1, sizeof(pre));
queue<int> q;
q.push(source);
vis[source] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = source; i <= terminal; i++) {
if (val[cur][i] > 0 && vis[i] == 0) {
vis[i] = 1;
pre[i] = cur;
//只要终端入队列就说明存在增广路,不用把终端入队列再出队列搜索一次
if (i == terminal) return true;
q.push(i);
}
}
}
return false;
};
//将每条增广路的流量全都累加起来
auto maxFlow = [=](int source, int terminal)->int {
int sum = 0;
//有增广路才统计流量
while (findPath(source, terminal)) {
//last,now用来回溯,每次都保持它们属于增广路上某条边的两个端点
int last = -1, now = terminal, mf = N;//N对于最终结果来说已经足够大了
while (now != source) {
last = pre[now];
//第一遍回溯,寻找决定最大流的关键边
mf = min(mf, val[last][now]);
now = last;
}
//实际上每个节点如果只匹配一次,那么此时的mf只能是1,可以直接sum++
sum += mf;
now = terminal;
while (now != source) {
last = pre[now];
//第二遍回溯,按顺序建立反向边用来回退
val[last][now] -= mf;
val[now][last] += mf;
now = last;
}
}
return sum;
};
//输出最大流量,也就是最大匹配数(最小点覆盖数)
cout << maxFlow(source, terminal) << endl;
}
return 0;
}
补充一点,这个EK算法的$maxFlow$函数是进阶篇网络流问题中的通用写法,在二分图匹配问题中,增广成功的条件下当前最大流$mf$只有可能是1,可以省略第一次回溯找关键边的步骤,$sum$自增后直接开始建立反向边(第二次回溯)