[BZOJ1143][CTSC2008]祭祀river 二分图最大匹配


原题链接
根据Dilworth定理,最长反链等于最小链覆盖
这个最小链覆盖是可重复经过一点的,为了转化成不能重复经过一个点,我们做一遍传递闭包
于是转化成了给定DAG选出最少的路径,每个点被经过正好一次
我们利用二分图匹配来求最小路径覆盖
将每个点拆成入点和出点,从每条边的出点向入点连边,构成一个二分图,则点数-最大匹配就是最小路径覆盖数

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;
int n,m,ans,f[N][N],v[N],belong[N],now;
int dfs(int x)
{
    for(int y=1;y<=n;++y)if(f[x][y]&&v[y]!=now)
    {
        v[y]=now;
        if(!belong[y]||dfs(belong[y]))
        {
            belong[y]=x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    int x,y,i,j,k;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        f[x][y]=1;
    }
    for(k=1;k<=n;++k)
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)f[i][j]|=f[i][k]&f[k][j];
    for(i=1;i<=n;++i)now++,ans+=dfs(i);
    cout<<n-ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注