BZOJ-1143: [CTSC2008]祭祀river

[文章目录]

Description

给你一张n个点,m条边的拓扑图,让你选出最多个数的点,使得没有任何两个你选的点A,B可及。 N<=100 M <=1 000

求的这个东西叫DAG的最长反链,它等于原图的最小可相交链覆盖。
求法为:对于原图每个点A,建新点A',对于可及两点A,B,由A向B'连边,形成二分图,点数减去这个二分图的最大匹配即为答案。
floyd+最大匹配
NOTE:
1.一个点也可以是一个链覆盖
2.最小不可相交链覆盖的求法和可相交的类似,不用floyd传递闭包。对于原图中的边A->B,二分图中连接A->B',点数减去这个二分图的最大匹配即为所求。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,ans;
bool mp[110][110];
int head[210],to[30000],nxt[30000],f[30000],cnt=1;
inline void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[210];
queue<int>q;
bool bfs()
{
    memset(dis,-1,sizeof dis);
    while(!q.empty()) q.pop();
    q.push(s); dis[s]=0; int x;
    while(!q.empty())
    {
        x=q.front(); q.pop();
        for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
        {
            dis[to[i]]=dis[x]+1;
            if(to[i]==t) return true;
            q.push(to[i]);
        }
    }
    return false;
}
int dinic(int x,int flow)
{
    if(x==t) return flow;
    int xx,tmp=flow;
    for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
    {
        xx=dinic(to[i],min(tmp,f[i]));
        if(!xx) dis[to[i]]=-1;
        f[i]-=xx; f[i^1]+=xx; tmp-=xx;
        if(!tmp) break;
    }
    return flow-tmp;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x,y; s=0; t=n+n+1;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        mp[x][y]=1;
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                mp[i][j]|=mp[i][k]&mp[k][j];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(mp[i][j]) add(i,n+j,1);
    for(int i=1;i<=n;++i) add(s,i,1),add(i+n,t,1);
    ans=n;
    while(bfs()) ans-=dinic(s,inf);
    printf("%d",ans);
    return 0;
}

发表评论

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