自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 21:56:46，当前版本为作者最后更新于2020-04-06 15:34:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

注意必须边$\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缩强连通分量,条件是:

• 可行边 : 两端不在一个强连通分量内。

• 必须边 : 一端在$S$的分量内,另一端在$T$的分量内。

#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;
}