<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
二分图匹配
这个问题可以说设置的非常好,它把最短路和最大流用“最小可相交路径点覆盖”的概念完美的串了起来
首先了解一下“最小不相交路径点覆盖”的求解方法:
对于DAG中的每一个节点$v$,首先将其拆开成为节点对$(v_l, v_r)$,将原图中的每一条边$(s, e)$改变为$(s_l, e_r)$,如此建模之后就形成了二分图,右半节点$v_r$对应的左半节点$v_l$如果没有出边就代表$v$是被选出来的路径终点,路径上的每条边就对应上了左半的某个节点$s_l$和右半某个节点$e_r$(不是$s_r$),由于每条路径都对应了唯一的终点,故最小不相交路径点覆盖就对应了一种匹配方式,使得左半的未匹配节点最少,这样就把问题转化为求二分图的最大匹配问题了
对于本问题中用到的“最小可相交路径点覆盖”,对原图求一下传递闭包之后,就转化为了不相交的路径点覆盖问题,求传递闭包要用最短路的Floyd算法,求最大匹配对数由于节点数不是很多,可以建立邻接矩阵,然后所有的$v_l$都被公共始端S连接,所有的$v_r$都连接到公共终端T,用什么算法不用多说了叭(
时间复杂度 $O(n*m^2)$
其实200节点数和3w边数,肯定是包含重边的
去掉重边之后,剩下的边数最多不会超过$n(n-1)/2$,可以一定程度上减少实际复杂度
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 405;
//path用来求传递闭包,其余用来求最大匹配值
int val[N][N], path[N / 2][N / 2], pre[N], vis[N];
int n, m, s, e;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
while (m--) {
cin >> s >> e;
path[s][e] = 1;
val[s][200 + e] = 1;
}
//求传递闭包之后会产生新边
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (path[i][k] == 1 && path[k][j] == 1) {
path[i][j] = 1;
val[i][200 + j] = 1;
}
}
}
}
//加上公共始端和公共终端
int source = 0, terminal = N - 1;
for (int i = 1; i <= n; i++) {
val[source][i] = val[200 + i][terminal] = 1;
}
//求最大匹配(其实就是求从始端S到终端T的网络最大流)
auto findPath = [=](int source, int terminal)->bool {
fill(vis, vis + N, 0);
fill(pre, pre + N, -1);
queue<int> q;
q.push(source);
vis[source] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < N; i++) {
if (vis[i] == 0 && val[cur][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)) {
int last = -1, now = terminal;
sum++;
while (now != source) {
last = pre[now];
val[last][now]--;
val[now][last]++;
now = last;
}
}
return sum;
};
//结果为节点总数减去最大匹配数(最大流量)
cout << n - maxFlow(source, terminal) << endl;
return 0;
}
Orz