题目概述

给出一张 $n$ 个点 $m$ 条有向边的图，现在要求 $S,T$ 的最小割，问每一条边：

1. 有没有可能出现在最小割中。
2. 是否一定出现在最小割中。

解题报告

先跑出随意一种最小割（最大流），然后在残量网络里缩点，接下来好像有结论？

• $(x,y)$ 可能出现：$SCC_x\not=SCC_y$ 。
• $(x,y)$ 一定出现：$SCC_S=SCC_x,SCC_y=SCC_T$ 。

yy一下还是挺显然的。因为缩点之后只剩下满流边，所以新图中每一种割都恰好对应原来的一种最小割，只要 $x,y$ 不在同一个强连通分量中，就可以被切断（从而形成某种最小割）；如果 $S$ 和 $x$ 在一起而 $y$ 和 $T$ 在一起，就说明 $(x,y)$ 必须切断才可能切断 $S$ 到 $T$ 。最后再注意一下流量为 $0$ 的边就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=4000,maxm=60000;

int n,m,S,T,x[maxm+5],y[maxm+5],z[maxm+5];
int dfn[maxn+5],low[maxn+5],top,stk[maxn+5],SCC[maxn+5];
int E,lnk[maxn+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5];
int cur[maxn+5],que[maxn+5],ti,vis[maxn+5],dis[maxn+5];
bool instk[maxn+5];pair<int,int> e[(maxm<<1)+5];

inline void Add(int x,int y,int z){
    son[E]=y;e[E]=mp(0,z);nxt[E]=lnk[x];lnk[x]=E++;
    son[E]=x;e[E]=mp(0,0);nxt[E]=lnk[y];lnk[y]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&e[j].fr<e[j].sc) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
    return vis[t]==ti;
}
int Dfs(int x,int gl,int MIN=2e9){
    if (x==gl||!MIN) return MIN;int f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],gl,min(MIN,e[j].sc-e[j].fr)))){
            f+=now;e[j].fr+=now;e[j^1].fr-=now;
            if (!(MIN-=now)) break;
        }
    return f;
}
void Tarjan(int x){
    dfn[x]=low[x]=++ti;stk[++top]=x;instk[x]=true;
    for (int j=lnk[x];~j;j=nxt[j])
        if (e[j].fr<e[j].sc)
            if (!dfn[son[j]]) Tarjan(son[j]),low[x]=min(low[x],low[son[j]]);
            else if (instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
    if (dfn[x]==low[x])
        for (int y=(SCC[0]++,stk[top--]);;y=stk[top--])
            {SCC[y]=SCC[0];instk[y]=false;if (x==y) break;}
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&S,&T);E=0;memset(lnk,255,sizeof(lnk));
    for (int i=1;i<=m;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]),Add(x[i],y[i],z[i]);
    while (Bfs(S,T)) memcpy(cur,lnk,sizeof(lnk)),Dfs(S,T);
    for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
    for (int i=1;i<=m;i++){
        if (e[i-1<<1].fr<e[i-1<<1].sc) {puts("0 0");continue;}
        putchar((SCC[x[i]]!=SCC[y[i]])+48);putchar(' ');
        putchar((SCC[S]==SCC[x[i]]&&SCC[y[i]]==SCC[T])+48);puts("");
    }
    return 0;
}