AcWing P379 捉迷藏 题解

Analysis

这道题因为我们要给能到达的两个点都连上，又由于n<=200，所以我们可以用n³的传递闭包来建边，再用匈牙利算法来求二分图最大点独立集。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 210
#define maxm 30010
using namespace std;
inline int read() 
{
    int x=0;
    bool f=1;
    char c=getchar();
    for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
    for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    if(f) return x;
    return 0-x;
}
inline void write(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,m,ans,match[maxm],cnt,tc[maxn][maxn];
bool book[maxm];
inline bool dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(tc[u][i]==1)
        {
            if(!book[i])
            {
                book[i]=1;
                if(!match[i]||dfs(match[i]))
                {
                    match[i]=u;
                    return true;
                }
            }
        }
        
    }
    return false;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=read();y=read();
        tc[x][y]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&tc[i][j]==0)
                {
                    tc[i][j]=tc[i][j]||(tc[i][k]&&tc[k][j]);
                }
    for(int i=1;i<=n;i++)
    {
        memset(book,0,sizeof(book));
        if(dfs(i))ans++;
    }
    write(n-ans);
    return 0;
}

请各位大佬斧正（反正我不认识斧正是什么意思）