题解 P4126 【[AHOI2009]最小割】

· · 题解

最小割的可行边和必须边(所有割集的交集和并集)

注意必须边\subseteq可行边.

显然,在某种最大流方案中,最小割\Rightarrow满流。

考虑现有的满流边 u,v 如何被替代,不难想到 : 残量网络中有包含 u,v 的环(另一条路,注意还包括反向边)。

让流沿着环流动一圈,最大流不变,但是满流被破坏。

由此引出 : 两个端点在同一强连通分量内的边必然总不是最小割。

将当前残量网络缩点成DAG,上面的边才有可能成为最小割。

在这些边里面,直接将S,T相连的我们必须要割,这些边就是必须边。

对于其他边都能分别够构造割与不割的方案,它们是可行边。

在这个DAG上,每一种紧的割(不考虑权值)都是最小割。

左端点 : 靠近S的一端, 右端点 : 靠近T的一端。

割的构造 : 把这条边左端点到 S 的路径钦定为 S 集合,其余为 T 集合,然后把所有 S,T 之间的边割断,这是紧的,而且该边是最小割的一部分。

不割的构造 : 如果右端点不是 T ,把这条边右端点到 S 的路径钦定为 S 集合。否则左端点必然不是 S ,把这条边左端点到 T 的路径钦定为 T 集合即可。这样整条边总是被完整地包含在 S 或 T 集中。

在这个DAG上搞搞说不定还有什么新科技……

具体实现,需要先跑最大流,然后Tarjan缩强连通分量,条件是:

#include<cstdio>
#include<vector>
#include<queue>
#define INF 1000000000 
#define MaxN 4050
#define MaxM 120500
using namespace std;
struct Line
{int to,nxt,cap;}l[MaxM];
int tl=1,fir[MaxN];
void add(int f,int t,int cap){
  l[++tl]=(Line){t,fir[f],cap};fir[f]=tl;
  l[++tl]=(Line){f,fir[t],0  };fir[t]=tl;
}
int S,T,n,dis[MaxN],cur[MaxN];
queue<int> q;
bool bfs()
{
  for (int i=1;i<=n;i++)
    {cur[i]=fir[i];dis[i]=0;}
  q.push(S);dis[S]=1;
  while(!q.empty()){
    int u=q.front();
    q.pop();
    for (int i=fir[u],v;i;i=l[i].nxt)
      if (l[i].cap&&!dis[v=l[i].to]){
        dis[v]=dis[u]+1;
        q.push(v);
      }
  }return dis[T];
}
int dfs(int u,int flow)
{
  if (u==T)return flow;
  int sum=0,sav,v;
  for (int &i=cur[u];i;i=l[i].nxt){
    if (dis[v=l[i].to]==dis[u]+1&&l[i].cap){
      sav=dfs(v,min(flow,l[i].cap));
      if (sav){
        l[i].cap-=sav;
        l[i^1].cap+=sav;
        sum+=sav;
        if (!(flow-=sav))return sum;
      }else dis[v]=-1;
    }
  }return sum;
}
int dfn[MaxN],low[MaxN],tim,
    stk[MaxN],top,col[MaxN],Bcnt;
bool in[MaxN];
void dfs2(int u)
{
  low[u]=dfn[u]=++tim;
  in[stk[++top]=u]=1;
  for (int i=fir[u],v;i;i=l[i].nxt)
    if (l[i].cap){
      if (!dfn[v=l[i].to])
        {dfs2(v);low[u]=min(low[u],low[v]);}
      else if (in[v])low[u]=min(low[u],dfn[v]);
    }
  if (low[u]==dfn[u]){
    Bcnt++;
    while(stk[top+1]!=u){
      in[stk[top]]=0;
      col[stk[top--]]=Bcnt;
    }
  }
}
int m,fr[MaxM],to[MaxM];
int main()
{
  scanf("%d%d%d%d",&n,&m,&S,&T);
  for (int i=1,cap;i<=m;i++){
    scanf("%d%d%d",&fr[i],&to[i],&cap);
    add(fr[i],to[i],cap);
  }while(bfs())dfs(S,INF);
  for (int i=1;i<=n;i++)
    if (!dfn[i])dfs2(i);
  for (int i=1;i<=m;i++)
    if (!l[i<<1].cap){
      printf("%d %d\n",
        col[fr[i]]!=col[to[i]],
        col[fr[i]]==col[S]&&col[to[i]]==col[T]
      );
    }else puts("0 0");
  return 0;
}