「BZOJ 1797」最小割

给定一个$n$个点$m$个点的有向图,对于每条边,需要回答

  • 是否可以是最小割中的一条边
  • 是否必须是最小割中的一条边

我们先考虑第一问. 我们先随意跑一个最小割,如果这条边可以存在于最小割,那么首先这条边一定是满流的,不妨设这条边是$u \rightarrow v$的,接下来我们考虑,如果这条边可以是最小割,我们从分别连接两条边$S \rightarrow u,v \rightarrow T$ 流量都是正无穷,最小割是不会变的,对应的考虑什么时候最小割会发生变化,一定是在参与网络上还存在一条从$u$指向$v$的路径,这样的话就还可以进行一次增广,这时候$u \rightarrow v$的反向弧会和那条路径构成一个强连通分量.也就是说,只要我们对残余网络把所有的$SCC$给求出来,只要保证一条边是满流的,同时两个端点属于不同的$SCC$,那么这条边就可以是割集中的一个.

接着考虑第二问,首先很明显必定在割集中的边一定满足一个端点在$S$集,一个点在$T$集.而对于在$S$中的点,既然这条边被割,那么一定存在一个从当前点到$S$的反向弧,同时存在从$S$到当前点的残余路径,所以肯定是属于$S$的强连通分量,简单判定一下即可.

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cmax(a,b)        a = max (a, b)
#define cmin(a,b)        a = min (a, b)
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

const int MAXN = 4e3 + 5;
const int MAXM = 6e4 + 5;
const int oo = 0x3f3f3f3f;

int N, M, S, T, dfn[MAXN], low[MAXN], bt[MAXN], sta[MAXN], top = 0, dfsclock = 0, scc = 0;
int ans[MAXM][2];
bool vis[MAXN];

namespace Maxflow{
    struct edge {
        int y, next, flow, rev;
    }e[MAXM << 1];
    int LINK[MAXN], len = 0, level[MAXN];
    deque<int> q;
    inline void ins(int x, int y, int flow, int rev){
        e[++len].next = LINK[x]; LINK[x] = len;
        e[len].y = y; e[len].flow = flow; e[len].rev = len + rev;
    }
    inline void Ins(int x, int y, int flow){
        ins(x, y, flow, 1);
        ins(y, x, 0, -1);
    }
    bool makelevel(){
        q.push_back(S);    
        fill(level, level + N + 1, -1);
        level[S] = 0;
        while (!q.empty()) {
            int node = q.front(); q.pop_front();
            Auto (i, node) if (level[e[i].y] == -1 && e[i].flow) {
                level[e[i].y] = level[node] + 1;
                q.push_back(e[i].y);
            }
        }
        return level[T] != -1;
    }
    int addflow(int node, int flow){
        if (node == T || !flow)    return flow;
        int maxflow = 0, d;
        Auto (i, node) if (level[e[i].y] == level[node] + 1 && e[i].flow) 
            if (d = addflow(e[i].y, min(e[i].flow, flow - maxflow))) {
                maxflow += d;
                e[i].flow -= d;
                e[e[i].rev].flow += d;
            }
        if (!maxflow) level[node] = -1;
        return maxflow;
    }
    void Dinic(){
        while (makelevel())
            while (addflow(S, oo));
    }
    void Tarjan(int node){
        dfn[node] = low[node] = ++dfsclock;
        vis[node] = 1; sta[++top] = node;
        Auto (i,node) if (e[i].flow) {
            if (!dfn[e[i].y]) {
                Tarjan(e[i].y);
                cmin (low[node], low[e[i].y]);
            } else if (vis[e[i].y]) cmin (low[node], dfn[e[i].y]);
        }
        if (dfn[node] == low[node]) {
            scc++;
            int tmp;
            do {
                tmp = sta[top--];
                vis[tmp] = 0;
                bt[tmp] = scc;
            }while (tmp != node);
        }
    }
}using namespace Maxflow;

namespace solution{
    void Prepare(){
        scanf("%d%d%d%d", &N, &M, &S, &T);
        up (i, 1, M) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            Ins(x, y, v);
        }
    }
    void Solve(){
        Dinic();
        up (i, 1, N) if (!dfn[i])
            Tarjan(i);
        up (node, 1, N) Auto(i, node) if(i & 1) {
            if (e[i].flow == 0) {
                if (bt[node] != bt[e[i].y]) ans[(i + 1) >> 1][0] = 1;
                if (bt[node] == bt[S] && bt[e[i].y] == bt[T]) ans[(i + 1) >> 1][1] = 1;
            } 
        } 
        up (i, 1, M) printf("%d %d\n", ans[i][0], ans[i][1]);
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}