BZOJ-1143-祭祀river(二分图-偏序集最大反链)

祭祀river

题意：

• 在有向无环图中找尽可能多的点使这些点任意两点都不能通过已知的边到达对方(最大反链(点集)) (区别最大点独立集)

思路：

• 最大反链==最小可相交路径覆盖

#include<bits/stdc++.h>
using namespace std;
int edge[110][110];
int match[110];
int vis[110];
int n,m;
void warshell(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(edge[i][j]==0)
            {
                for(int k=1;k<=n;k++)
                {
                    if(edge[i][k]&&edge[k][j])
                    {
                        edge[i][j]=1;
                    }
                }
            }
        }
    }
}
int Hungarian(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&edge[x][i])
        {
            vis[i]=1;
            if(match[i]==-1||Hungarian(match[i]))
            {
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main( )
{
    int x,y;
    scanf("%d%d",&n,&m);
    memset(edge,0,sizeof(edge));
    memset(match,-1,sizeof(match));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        edge[x][y]=1;
    }
    warshell(n);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(Hungarian(i))
        {
            ans++;
        }
    }
    printf("%d\n",n-ans);
    return 0;
}

BZOJ-1143-祭祀river(二分图-偏序集最大反链)

原文：https://www.cnblogs.com/lcbwwy/p/13125120.html