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

Problem

【AHOI2009】Mincut最小割

Description

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

Input

第一行有个正整数，依次为。
第行到第行每行个正整数表示中转站到中转站之间有单向道路相连，单向道路的起点是，终点是，切断它的代价是。
注意：两个中转站之间可能有多条道路直接相连。
同一行相邻两数之间可能有一个或多个空格。

Output

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

Sample Input

Sample Output

Explanation

设第行输入的边为号边，那么是仅有的三个最小代价切割方案。
它们的并是，交是。

HINT

新加数据一组，可能会卡掉从前可以过的程序。

标签：网络流 Tarjan

Solution

考察最小割性质的裸题。

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

综上，跑网络流后在残余网络跑，记第个点的强连通分量编号为，则对于边，满足第一问当且仅当，满足第二问当且仅当且。

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