【洛谷】P10938 Vani和Cl2捉迷藏 的题解

【洛谷】P10938 Vani和Cl2捉迷藏 的题解

洛谷传送门

题解

噢噢噢噢哦哦哦，神奇网络流，有点像 Floyd

在图上选取若干条互不相交的路径，并让这些路径不重不漏覆盖到每一个点。符合上述要求且总数最小的方案就叫做原图的最小路径点覆盖，图中每个节点均只被覆盖一次。而最小重复路径点覆盖则是允许选取的路径相交，即某个点至少被覆盖一次。

在二分图中，最小路径点覆盖的路径条数等于总点数减去最大匹配数；最小路径重复点覆盖的数量则需要先求传递闭包（有点类似 Floyd），再计算最小路径点覆盖得出答案，输出即可。

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {inline int read() {register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;}inline void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;}
}
using namespace fastIO;
bool cl[225][225], vis[225];
int match[225], n, m;
bool dfs(int x) {for(int i = 1; i <= n; i ++) {if(cl[x][i] && !vis[i]) {vis[i] = true;if(!match[i] || dfs(match[i])) {match[i] = x;return true;}}}return false;
}
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read(), m = read();for(int i = 1; i <= m; i ++) {int x = read(), y = read();cl[x][y] = 1;}for(int i = 1; i <= n; i ++) {cl[i][i] = 1;}for(int k = 1; k <= n; k ++) {for(int i = 1; i <= n; i ++) {for(int j = 1; j <= n; j ++) {cl[i][j] |= cl[i][k] && cl[k][j];}}}for(int i = 1; i <= n; i ++) {cl[i][i] = 0;}int ans = n;for(int i = 1; i <= n ; i ++) {memset(vis, 0, sizeof(vis));ans -= dfs(i);}write(ans);return 0;
}