CodeVS2494 Vani和Cl2捉迷藏

题意

在 $N$ 点 $M$ 边的有向无环图中选出最多的点，要求这些点两两之间不能有路径相连。

$N\le 200$ ，$M\le 30000$ 。

题解

路径可达的关系可以通过 $\text{Floyd}$ 传递闭包处理。

剩下的问题即转化为：选出最多的点，要求这些点两两没有连边。

如果把每个点分裂成两个点，形成二分图，就是标准的最大独立集问题。最大独立集 $= N - $ 最小点覆盖（最大匹配）。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

bool vis[205],s[205][205];
int n,m,a,b,mch[205];

bool find(int x)
{
    for (int y=1;y<=n;y++)
    {
        if (!s[x][y] || vis[y]) continue;
        vis[y]=1;
        if (!mch[y] || find(mch[y])) return mch[y]=x,1;
    }
    return 0;
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        s[a][b]=1;
    }
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                s[i][j]|=s[i][k]&s[k][j];
    int ans=n;
    for (int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        ans-=find(i);
    }
    return !printf("%d",ans);
}