题解：P10938 Vani和Cl2捉迷藏

_OccDreamer_ · 2025-02-21 16:38:33 · 题解

题意

最小可交路径点覆盖。

前置知识

最小无交路径点覆盖。

令最小无交路径点覆盖数为 x，二分图最大匹配数为 y，图总点数为 n。

结论是：x = n - y。

思路

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

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

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

代码：

#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;
}