2021-08-05

AOJ 2594 Reverse a Road II (JAG 模擬地区 2014 F) (600 点)

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね！！

問題概要

頂点数 $N$ 、辺数 $M$ の有向グラフ $G$ と、2 頂点 $s, t$ が与えられます。

いま、グラフの辺を 1 本選んで向きを反転させます。それによって、 $s$ - $t$ 間の辺連結度を増やしたいと考えています。辺の向きを反転させることで辺連結度が増大するような辺が何本あるかを求めてください。

制約

$2 \le N \le 1000$
$1 \le M \le 10000$

考えたこと

さて、まず愚直な解法として思いつくのは「各辺を 1 本ずつ flip していって、その都度最大流を流す」という方法でしょう。しかしこれでは流石に TLE してしまいます。

このような問題では、まずは普通に最大流問題を解いてみることが有効です。そしてその結果を活用することで、解きたい問題も効率よく解決できないかを考えてみましょう。

最大流を流し終えた段階では、残余グラフ上において、頂点 $s$ から到達可能な頂点集合を $S$ としたとき、 $s \notin S$ となっています。これは「最大流値 = 最小カット値」という有名な最大流-最小カット定理を証明するときによくやる論法です！！

また逆に残余グラフ上において、頂点 $t$ へと到達可能な頂点集合を $T$ としましょう。このとき $S \cup T = V$ とは限らないことに注意しましょう ( $V$ はグラフ $G$ の頂点集合)。 $s$ から到達できないし、そこから $t$ にも至らないような頂点が存在することもありえるからです。なお、 $U = V - S - T$ としておきます。

残余グラフに関する考察

さて、残余グラフ上において始点が $T$ 側にあって終点が $S$ 側にあるような辺に注目しましょう。このような辺は

もともと $S$ から $T$ へ向かう辺であったが $s$ - $t$ パスとして選ばれた結果、残余グラフ上で向きが反転した辺
もともと $T$ から $S$ へ向かう辺であって、 $s$ - $t$ パスとして選ばれなかった辺

に分かれます。このうちの後者については、 flip することで新たに $s$ - $t$ パスが生成されます。

さて、それ以外に $s$ - $t$ 間の辺連結度の増大に寄与する辺は存在するでしょうか？　まず $s$ - $t$ パスとして使用された辺以外のうち、

両端点が $S$ に含まれるような辺
両端点が $T$ に含まれるような辺
少なくとも一方の端点が $U$ に含まれるような辺

については、flip しても、残余グラフ上で $s$ - $t$ パスが新たに生じることはないことがわかります (連結度が減少することはありえます)。よって除外して考えて良いです。

最後に、 $s$ - $t$ パスに含まれる辺を flip した場合のことを考えてみましょう。このとき、その両端点が $S$ に含まれる辺や両端点が $T$ に含まれる辺については、flip しても最小カットが増えることはありえません。また、元のグラフでは $S$ から $T$ へと伸びている辺 (残余グラフ上では $T$ から $S$ へと伸びている辺) については、flip することでむしろ辺連結度は減少することがわかります。

以上から、残余グラフ上で始点が $T$ 側にあって終点が $S$ 側にあるような辺のうち、 $s$ - $t$ パスに使われていない辺の本数が答えとなりことがわかりました。

計算量は最初に最小カットを求める部分がボトルネックとなります。一度だけ最大流問題を解くだけの計算量となりますので、十分高速です。

コード

#include <bits/stdc++.h>
using namespace std;

// グラフを表す構造体
struct Graph {
    // 辺を表す構造体
    // rev: 逆辺 (to, from) が G[to] の中で何番目の要素か
    // cap: 辺 (from, to) の容量 (この値は変化する)
    // icap: 辺 (from, to) のもともとの容量
    struct Edge {
        int rev, from, to, cap, icap;
        Edge(int r, int f, int t, int c) :
            rev(r), from(f), to(t), cap(c), icap(c) {}
    };

    // 隣接リスト
    vector<vector<Edge>> list;

    // N: 頂点数
    Graph(int N = 0) : list(N) { }

    // グラフの頂点数取得
    size_t size() {
        return list.size();
    }
    
    // Graph インスタンスを G として，
    // G.list[v] を G[v] と書けるようにしておく
    vector<Edge> &operator [] (int i) {
        return list[i];
    }

    // 辺 e = (u, v) の逆辺 (v, u) を取得する
    Edge& redge(const Edge &e) {
        return list[e.to][e.rev];
    }

    // 辺 e = (u, v) に流量 f のフローを流す
    // e = (u, v) の流量が f だけ減少する
    // このとき逆辺 (v, u) の流量を増やす
    void run_flow(Edge &e, int f) {
        e.cap -= f;
        redge(e).cap += f;
    }

    // 頂点 from から頂点 to へ容量 cap の辺を張る
    // このとき to から from へも容量 0 の辺を張っておく
    void addedge(int from, int to, int cap) {
        int fromrev = (int)list[from].size();
        int torev = (int)list[to].size();
        list[from].push_back(Edge(torev, from, to, cap));
        list[to].push_back(Edge(fromrev, to, from, 0));
    }
};

struct FordFulkerson {
    static const int INF = 1 << 30; // 無限大を表す値を適切に
    vector<int> seen;

    FordFulkerson() { }

    // 残余グラフ上で s-t パスを見つける (深さ優先探索)
    // 返り値は s-t パス上の容量の最小値 (見つからなかったら 0)
    // f: s から v へ到達した過程の各辺の容量の最小値
    int fodfs(Graph &G, int v, int t, int f) {
        // 終端 t に到達したらリターン
        if (v == t) return f;

        // 深さ優先探索
        seen[v] = true;
        for (auto &e : G[v]) {
            if (seen[e.to]) continue;

            // 容量 0 の辺は実際には存在しない
            if (e.cap == 0) continue;

            // s-t パスを探す
            // 見つかったら flow はパス上の最小容量
            // 見つからなかったら f = 0
            int flow = fodfs(G, e.to, t, min(f, e.cap));

            // s-t パスが見つからなかったら次辺を試す
            if (flow == 0) continue;

            // 辺 e に容量 flow のフローを流す
            G.run_flow(e, flow);

            // s-t パスを見つけたらパス上最小容量を返す
            return flow;
        }

        // s-t パスが見つからなかったことを示す
        return 0;
    }

    // グラフ G の s-t 間の最大流量を求める
    // ただしリターン時に G は残余グラフになる
    int solve(Graph &G, int s, int t) {
        int res = 0;

        // 残余グラフに s-t パスがなくなるまで反復
        while (true) {
            seen.assign((int)G.size(), 0);
            int flow = fodfs(G, s, t, INF);

            // s-t パスが見つからなかったら終了
            if (flow == 0) return res;

            // 答えを加算
            res += flow;
        }

        // no reach
        return 0;
    }
};

void solve(Graph &G, int N, int s, int t) {
    // 一旦フローを流す
    FordFulkerson ff;
    int B = ff.solve(G, s, t);
    
    // s から到達可能な頂点、t へ到達可能な頂点
    vector<int> S(N, false), T(N, false);
    queue<int> que;
    que.push(s);
    S[s] = true;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto e: G[v]) {
            if (e.cap > 0 && !S[e.to]) {
                S[e.to] = true;
                que.push(e.to);
            }
        }
    }
    que.push(t);
    T[t] = true;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto e: G[v]) {
            // 逆辺があるとき
            if (G.redge(e).cap > 0 && !T[e.to]) {
                T[e.to] = true;
                que.push(e.to);
            }
        }
    }
    
    // T から S へ向かう辺数のうち、s-t パスに使われなかった辺数
    int res = 0;
    for (int v = 0; v < N; ++v) {
        if (T[v]) {
            for (auto e: G[v]) {
                if (e.cap > 0 && e.cap == e.icap && S[e.to]) ++res;
            }
        }
    }
    
    // 答え
    int ma = (res ? B + 1 : B);
    cout << ma << " " << res << endl;   
}

int main() {
    // 入力
    int N, M, s, t;
    while (cin >> N >> M >> s >> t) {
        if (N == 0) break;
        --s, --t;
        Graph G(N);
        for (int i = 0; i < M; ++i) {
            int a, b;
            cin >> a >> b;
            --a, --b;
            G.addedge(a, b, 1);
        }
        solve(G, N, s, t);
    }
}