[BZOJ2893]征服王 tarjan缩点 最小流


原题链接
给一张有向图,一部分点可以作为起点,一部分点可以作为终点,要求用最小次数遍历完所有边.
直接tarjan缩点,然后就是最小流板子题.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 5023
#define M 202333
#define mem(x) memset(x,0,sizeof x)
using namespace std;
const int inf=0x3bbbbbbb;
int n,m,head[N],to[M],nxt[M],f[M],tot,lim;
inline void add1(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
inline void add2(int x,int y,int z)
{
    to[++tot]=y,nxt[tot]=head[x],head[x]=tot,f[tot]=z;
    to[++tot]=x,nxt[tot]=head[y],head[y]=tot,f[tot]=0;
}
int n1,n2,v1[N],v2[N];
int low[N],dfn[N],tim,z[N],inz[N],belong[N],top,cnt;
void tarjan(int x)
{
    low[x]=dfn[x]=++tim;
    z[++top]=x,inz[x]=1;
    int i,y;
    for(i=head[x];i;i=nxt[i])
    {
        y=to[i];
        if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
        else if(inz[y])low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        cnt++;
        int t;
        do
        {
            t=z[top--];
            inz[t]=0;
            v1[n+cnt]|=v1[t],v2[n+cnt]|=v2[t];
            belong[t]=cnt;
        }while(t!=x);
    }
}
int q[N],dis[N],l,r;
inline bool bfs(int s,int t)
{
    memset(dis,0,sizeof dis);
    l=1,r=1,q[r]=s,dis[s]=1;
    int i,x,y;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i>lim;i=nxt[i])if(f[i]&&dis[y=to[i]]==0)
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q[++r]=y;
        }
    }
    return 0;
}
int dinic(int t,int x,int flow)
{
    if(x==t)return flow;
    int i,y,lft=flow,tmp;
    for(i=head[x];i>lim;i=nxt[i])if(f[i]&&dis[y=to[i]]==dis[x]+1)
    {
        tmp=dinic(t,y,min(lft,f[i]));
        if(!tmp)dis[y]=0;
        f[i]-=tmp,f[i^1]+=tmp;
        lft-=tmp;
        if(!lft)return flow;
    }
    return flow-lft;
}
inline int maxflow(int s,int t)
{
    int re=0;
    while(bfs(s,t))re+=dinic(t,s,inf);
    return re;
}
int s,t,ss,tt;
inline int p1(int x){return x+n;}
inline int p2(int x){return x+n+cnt;}
void build()
{
    int x,y,i;
    for(i=1;i<=n;++i)if(!dfn[i])tarjan(i);
    if(!(tot&1))tot++;
    lim=tot,s=n+2*cnt+1,t=s+1,ss=t+1,tt=ss+1;
    for(x=1;x<=n;++x)
    {
        for(i=head[x];i;i=nxt[i])if(belong[y=to[i]]!=belong[x])
            add2(p2(belong[x]),p1(belong[y]),inf);
    }
    add2(t,s,inf);
    for(i=1;i<=cnt;++i)if(v1[p1(i)])
        add2(s,p1(i),inf);
    for(i=1;i<=cnt;++i)if(v2[p1(i)])
        add2(p2(i),t,inf);
    for(i=1;i<=cnt;++i)
    {
        add2(p1(i),p2(i),inf);
        add2(p1(i),tt,1);
        add2(ss,p2(i),1);
    }
}
void init()
{
    mem(head);
    tot=0;
    mem(v1),mem(v2);
    mem(low),mem(dfn),tim=cnt=0;
}
void getans()
{
    maxflow(ss,tt);
    int x,i,ans,flag=0;
    for(i=head[t];i>lim;i=nxt[i])if(to[i]==s)
    {
        ans=f[i^1];
        f[i]=f[i^1]=0;
    }
    for(i=head[ss];i>lim;i=nxt[i])
    {
        if(f[i])flag=1;
        f[i]=f[i^1]=0;
    }
    if(flag)
    {
        puts("no solution");
        return;
    }
    for(i=head[tt];i;i=nxt[i])f[i]=f[i^1]=0;
    ans-=maxflow(t,s);
    cout<<ans<<endl;
}
int T;
int main()
{
    cin>>T;
    int i,x,y;
    while(T--)
    {
        init();
        cin>>n>>m>>n1>>n2;
        for(i=1;i<=n1;++i)
        {
            scanf("%d",&x);
            v1[x]=1;
        }
        for(i=1;i<=n2;++i)
        {
            scanf("%d",&x);
            v2[x]=1;
        }
        for(i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            add1(x,y);
        }
        build();
        getans();
    }
    return 0;
}
/*
2

2 1 1 1

1

2

2 1

3 2 3 3

1 2 3

1 2 3

1 2

1 3
*/

发表评论

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