题解：P10938 Vani和Cl2捉迷藏

题意

最小可交路径点覆盖。

前置知识

最小无交路径点覆盖。

令最小无交路径点覆盖数为

x

，二分图最大匹配数为

y

，图总点数为

n

。

结论是：

x = n - y

。

思路

考虑转化。如果一个点可以间接到达另一个点，那么在图上建一条直接连接两点的边，做最小无交路径点覆盖就相当于原先的最小可交路径点覆盖。

这个证明是很好想的，可以自行思考。

对于判断一个点是否可以间接到达另一个点，用 Floyd 做传递闭包即可。

代码：

CPP

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

const int N = 205;
int n, m, u, v, mch[N], dis[N][N];
bool vis[N];
vector<int> g[N];

inline bool dfs(int x) {
	for(auto u : g[x])
		if(! vis[u]) {
			vis[u] = true;
			
			if(! mch[u] || dfs(mch[u])) {
				mch[u] = x;
				
				return true;
			}
		}
	
	return false;
}

signed main() {
	ios_base :: sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 1 ; i <= m ; ++ i) {
		cin >> u >> v;
		
		dis[u][v] = true;
	}
	
	for(int k = 1 ; k <= n ; ++ k)
		for(int i = 1 ; i <= n ; ++ i)
			for(int j = 1 ; j <= n ; ++ j)
				dis[i][j] |= (dis[i][k] & dis[k][j]);
	
	for(int i = 1 ; i <= n ; ++ i)
		for(int j = 1 ; j <= n ; ++ j)
			if(dis[i][j]) g[i].pb(j);
	
	int ans = 0;
	
	for(int i = 1 ; i <= n ; ++ i) {
		memset(vis, false, sizeof vis);
		
		if(dfs(i)) ++ ans;
	}
	
	cout << n - ans;
	
	return 0;
}

题解：P10938 Vani和Cl2捉迷藏

文章操作

题意

前置知识

思路

相关推荐

评论

题解：P10938 Vani和Cl2捉迷藏