dwjshift's Blog

bzoj1797 [Ahoi2009]Mincut 最小割

| Comments

显然要先跑一边最大流。然后我们可以得出以下结论:
(1)在残量网络中,能够到达的节点一定会被归入割。
(2)在残量网络中,能够到达的节点一定会被归入割。
(3)剩余的节点可能被归入割,也可能被归入割。
为什么呢?节点一定会被归入割,等价于节点不可能被归入割。我们强制把节点归入割,即从连一条容量为的边。那么在残量网络中,若能够到达节点,就会出现一条新的增广路,导致最小割变大。因此,就一定会被归入割。(2)也是同理,那显然就可以得出(3)了。

对于第一个问,只要边满足不一定被归入割,不一定被归入割,这条边就有可能被割去。那么第一问就完美解决啦(鼓掌熊
……吗?
事实上,这样做连样例都过不了(不过其实是能A的……数据太水了……)。这样判断包含了一种情况:,都不确定归入哪一个割。但是,有可能是绑定在一起的,也就是说必定会被分到同一个割,那这条边是永远不可能被割掉的。所以我们必须换一种做法。
假设强制把边割去,即从连一条容量为的边,从连一条容量为的边,若残量网络中有从的路径,就会导致最小割变大。因此,仅当残量网络中没有的路径,且可能被归入割、可能被归入割时,这条边才有可能被割去。另外,由于残量网络中不能有的路径,显然只有当边为满流时,它才有可能被割去。此时,残量网络中就有的反向弧,若有一条从的路径,它们就会构成一个强联通分量。所以我们可以先把残量网络缩点,然后对于每条满流的边(满流就能保证可能被归入割、可能被归入割)判断一下,若不在同一个强联通分量中,这条边就有可能被割去。那么第一问终于解决啦>.<

解决完第一问后第二问就显得很水了。只要一定被归入割,一定被归入割,这条边就必定被割去。那需要再单独写个dfs吗?其实是不需要的。由于满流了,那就一定会有一条从的增广路,若残量网络中还有从的路径,它就会和这条增广路的反向弧组成强联通分量。那边也是同理。所以可以直接对于每条边判断一下,若在同一个强联通分量,在同一个强联通分量,这条边就必定被割去。

code

#include <cstdio>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

int n,m,s,t,u,v,c,dis[4100],gap[4100],low[4100],rea[4100],cnt,
flag[4100],top,stk[4100],tot,lab[4100];
struct edge
{
    int v,flow;
    edge *nxt,*rev;
} pool[120100],*tp=pool,*fst[4100],*cur[4100];

int sap(int x,int flow)
{
    if (x==t)
        return flow;
    int sum=0,f;
    for (edge *i=cur[x]; i; i=i->nxt)
        if (i->flow && dis[x]==dis[i->v]+1)
        {
            f=sap(i->v,min(flow-sum,i->flow));
            i->flow-=f,i->rev->flow+=f,cur[x]=i;
            if ((sum+=f)==flow || dis[s]==n)
                return sum;
        }
    if (!(--gap[dis[x]]))
        dis[s]=n;
    ++gap[++dis[x]],cur[x]=fst[x];
    return sum;
}

void dfs(int x)
{
    low[x]=rea[x]=++cnt,stk[++top]=x,flag[x]=1;
    for (edge *i=fst[x]; i; i=i->nxt)
        if (i->flow)
        {
            if (!flag[i->v])
                dfs(i->v);
            if (flag[i->v]<2)
                low[x]=min(low[x],low[i->v]);
        }
    if (rea[x]==low[x])
        for (++tot; stk[top+1]!=x; lab[stk[top]]=tot,flag[stk[top--]]=2);
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    repu(i,1,m)
    {
        scanf("%d%d%d",&u,&v,&c);
        *tp=(edge){v,c,fst[u],tp+1},fst[u]=tp++;
        *tp=(edge){u,0,fst[v],tp-1},fst[v]=tp++;
    }
    gap[0]=n;
    repu(i,1,n)
        cur[i]=fst[i];
    for (; dis[s]<n; sap(s,1<<30));
    repu(i,1,n)
        if (!flag[i])
            dfs(i);
    for (edge *i=pool; i<tp; i+=2)
    {
        printf("%d ",!i->flow && lab[i->rev->v]!=lab[i->v]);
        printf("%d\n",lab[i->rev->v]==lab[s] && lab[i->v]==lab[t]);
    }
    return 0;
}

Comments

comments powered by Disqus