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

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空