BZOJ1797【AHOI2009】Mincut最小割 <网络流+Tarjan>

Problem

【AHOI2009】Mincut最小割

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$\mathrm{A,B}$两个国家正在交战，其中$\mathrm{A}$国的物资运输网中有$N$个中转站，$M$条单向道路。
设其中第$i$ $(1\le i\le M)$条道路连接了$v_i,u_i$两个中转站，那么中转站$v_i$可以通过该道路到达$u_i$中转站，如果切断这条道路，需要代价$c_i$。
现在$\mathrm{B}$国想找出一个路径切断方案，使中转站$s$不能到达中转站$t$，并且切断路径的代价之和最小。
小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：
问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？
问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？
请你回答这两个问题。

Input

第一行有$4$个正整数，依次为$N,M,s,t$。
第$2$行到第$(M+1)$行每行$3$个正整数$v,u,c$表示$v$中转站到$u$中转站之间有单向道路相连，单向道路的起点是$v$，终点是$u$，切断它的代价是$c$。
注意：两个中转站之间可能有多条道路直接相连。
同一行相邻两数之间可能有一个或多个空格。

Output

对每条单向边，按输入顺序，依次输出一行，包含两个非$0$即$1$的整数，分别表示对问题一和问题二的回答（其中输出$1$表示是，输出$0$表示否）。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

Sample Input

6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3

Sample Output

1 0
1 0
0 0
1 0
0 0
1 0
1 0

Explanation

设第$(i+1)$行输入的边为$i$号边，那么$\lbrace1,2\rbrace,\lbrace6,7\rbrace,\lbrace2,4,6\rbrace$是仅有的三个最小代价切割方案。
它们的并是$\lbrace1,2,4,6,7\rbrace$，交是$\phi$。

HINT

$N\le4\times10^3,M\le6\times10^4,1\le c\le10^5$
$\mathrm{2015.4.16}$新加数据一组，可能会卡掉从前可以过的程序。

标签：网络流 Tarjan

Solution

考察最小割性质的裸题。

首先跑网络流，通过残余网络可以看出哪些边是满载的（即剩余流量为$0$），将这些边去掉后跑$\mathrm{Tarjan}$，得到若干个强连通分量。
对于第一问，若一条边的两端点在不同强连通分量中，则一定存在方案使其被切断。这是因为出现这种情况时，这条边一定是所有从$s$到$t$且包含这条边的链中边权最小的边之一（即容量为阀值），那么若想断掉这条链，一定可以通过割这条边达到最小花费。
对于第二问，首先肯定要有第一问的条件，此外，需要$u$和$s$在同一强连通分量中，$v$和$t$在同一强连通分量中。这时由于在一条从$s$到$t$的链上，边权为阀值的所有边都会满载，而这条边必须被割掉当且仅当其是这条链上唯一边权为阀值的边，对应地，这代表着这条链上只有这条边是断的，即两端点分别在$s$和$t$所在的强连通分量中。

综上，跑网络流后在残余网络跑Tarjan，记第$i$个点的强连通分量编号为$id_i$，则对于边$(u,v)$，满足第一问当且仅当$id_u\ne id_v$，满足第二问当且仅当$id_u=id_s$且$id_v=id_t$。

Code

#include <bits/stdc++.h>
#define MAX_N 4000
#define MAX_M 60000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
int dfn[MAX_N+5], low[MAX_N+5], col[MAX_N+5], ind, tot;
struct edge {int v, c, nxt;} E[MAX_M*2+5];
stack <int> sta; bool insta[MAX_N+5];
void init() {read(s), read(t), cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (edge){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que; que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow; int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1; return ret;
}
void cpy() {for (int i = 1; i <= n; i++) cr[i] = pr[i];}
void rec() {for (int i = 1; i <= n; i++) pr[i] = cr[i];}
void Dinic() {cpy(); while (BFS()) DFS(s, INF), rec();}
void tarjan(int u) {
    dfn[u] = low[u] = ++ind, sta.push(u), insta[u] = true;
    for (int i = pr[u], v; ~i; i = E[i].nxt) if (E[i].c) {
        if (!dfn[v = E[i].v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (insta[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        tot++;
        for (int i = sta.top(); ; i = sta.top()) {
            col[i] = tot, insta[i] = false;
            sta.pop(); if (u == i) break;
        }
    }
}
int main() {
    read(n), read(m), init();
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), addedge(u, v, c);
    Dinic();
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    s = col[s], t = col[t];
    for (int i = 0; i < cnt; i += 2) {
        if (E[i].c) {puts("0 0"); continue;}
        int u = col[E[i^1].v], v = col[E[i].v];
        printf("%d %d\n", (u != v), (u == s && v == t));
    }
    return 0;
}