题意

求最小割和可行边和必须边。

思路

清真，清真，还是 ** 的清真。

考虑可行边的充要条件：

1. 满流

2. 不存在另一条 \(u, v\) 间的最短路，即在残量网络上不存在包含 \(u, v\) 的环

根据最小割最大流定理有最小割容量等于最大割流量。

因为跑完一遍最短路之后残量网络中不存在增广路，所以割掉所有满流的边以后 \(S, T\) 一定不连通。

又因为在一条已经增广完的路径上，割掉满流边的代价一定优于非满流边的代价，所以只割满流边一定可以构造出最小割，并且割非满流边一定不是最小割。

如果在一种方案中 \((u, v)\) 满流，但是存在另一条 \(u, v\) 之间的增广路径（环），那么只需要分出一部分流量在这条路径上流一次就可以破坏掉 \((u, v)\) 的满流。

判 2 可以用 tarjan 缩点，如果在同一 scc 中就说明有环。

考虑必须边的充要条件：

1. 是可行边

2. 不割掉它一定会导致 \(S, T\) 连通

所以在可行边的基础上特判一下 \(u, v\) 所属的连通分量就行。

具体构造见 题解 P4126 【[AHOI2009]最小割】 orz cmd

时间复杂度 O(飞快)

代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 4e3 + 5;
const int maxm = 6e4 + 5;
const int maxe = 2e5 + 5;
const int inf = 0x3f3f3f3f;

struct node
{
    int to, nxt, w;
} edge[maxe];

struct item
{
    int u, v, w;
} e[maxm];

int n, m, s, t, cnt = 1;
int head[maxn], bel[maxn];

void add_edge(int u, int v, int w)
{
    edge[++cnt] = (node){v, head[u], w};
    head[u] = cnt;
}

namespace net_flow
{
    int dep[maxn], cur[maxn];

    bool bfs()
    {
        queue<int> q;
        memset(dep, 0, (n + 1) * sizeof(int));
        dep[s] = 1;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; i; i = edge[i].nxt)
            {
                int v = edge[i].to;
                if (edge[i].w && (!dep[v]))
                {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return (dep[t] > 0);
    }

    int dfs(int u, int dis)
    {
        if (u == t) return dis;
        for (int &i = cur[u]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (edge[i].w && (dep[v] == dep[u] + 1))
            {
                int dist = dfs(v, min(dis, edge[i].w));
                if (dist)
                {
                    edge[i].w -= dist, edge[i ^ 1].w += dist;
                    return dist;
                }
            }
        }
        return 0;
    }

    int dinic()
    {
        int ans = 0;
        while (bfs())
        {
            int dis;
            memcpy(cur, head, (n + 1) * sizeof(int));
            while (dis = dfs(s, inf)) ans += dis;
        }
        return ans;
    }
}

namespace tarjan
{
    int cnt = 0, cur = 0;
    int top, stk[maxn];
    int low[maxn], dfn[maxn];
    bool in_stk[maxn];

    void pop(int idx)
    {
        int v = stk[top--];
        in_stk[v] = false;
        bel[v] = idx;
    }

    void tarjan(int u)
    {
        low[u] = dfn[u] = ++cnt;
        stk[++top] = u;
        in_stk[u] = true;
        for (int i = head[u]; i; i = edge[i].nxt)
        {
            if (!edge[i].w) continue;
            int v = edge[i].to;
            if (!dfn[v])
            {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u])
        {
            cur++;
            while (stk[top] != u) pop(cur);
            pop(cur);
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1, u, v, c; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &c);
        e[i] = (item){u, v, c};
        add_edge(u, v, c);
        add_edge(v, u, 0);
    }
    net_flow::dinic();
    for (int i = 1; i <= n; i++)
        if (!tarjan::dfn[i]) tarjan::tarjan(i);
    for (int i = 1; i <= m; i++)
    {
        if (edge[i << 1].w)
        {
            puts("0 0");
            continue;
        }
        putchar(bel[e[i].u] != bel[e[i].v] ? '1' : '0');
        putchar(' ');
        putchar(((bel[e[i].u] == bel[s]) && (bel[e[i].v] == bel[t])) ? '1' : '0');
        putchar('\n');
    }
    return 0;
}