题解：P10938 Vani和Cl2捉迷藏

_recollector_ · 2025-01-16 08:30:15 · 题解

不难发现，这个图 G 是一个 DAG。

而这 k 个点都没有路径相连，则从任一入度为 0 的点到达这个点只有一条路径，而路径之间可以重复，于是就变成了可重边的 DAG 最小路径覆盖问题。

用 Floyd 传递闭包，变成不可重边的 DAG 最小路径覆盖问题，然后直接跑匈牙利算法即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205;
int n,m;
int mp[N][N];
int mat[N],vis[N];
bool dfs(int u)
{
    for(int i=1;i<=n;++i)
    {
        if(!mp[u][i]||vis[i]) continue;
        vis[i]=1;
        if(!mat[i]||dfs(mat[i]))
        {
            mat[i]=u;
            return 1;
        }
    }
    return 0;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        cin>>x>>y;
        mp[x][y]=1;
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                mp[i][j]|=(mp[i][k]&mp[k][j]);
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        memset(vis,0,sizeof vis);
        ans+=dfs(i);
    }
    cout<<n-ans;
}