ACPC 2020 day1 F - コマの配置

3198 < VPC TUATPC < Challenges | Aizu Online Judge

問題

$N \times N$ のグリッドがある。最初、そのうち $M$ マスが白マスで、それ以外が黒マスになっている。

グリッドに対して $Q$ 回の変更が行われる。各変更では 1 つのマスが指定され、そのマスの色を白黒反転させる。

各変更直後について、白マスに $N$ 個のコマを置くことで、各行・各列にコマがちょうど 1 つずつ置かれているようにできるか判定せよ。

制約

$1 \leq N, M, Q \leq 5 \cdot 10^3$

考察

マッチングへの帰着

まず各行・列に対応する頂点を $N$ 個ずつ用意し、各白マス $(r, c)$ について、行側の頂点 $r$ と列側の頂点 $c$ を繋ぐ辺を張る。するとこのグラフは $2N$ 頂点 $M$ 辺の二部グラフとなり、「コマの置き方」が「辺の選び方」と対応する。

そして問題文中の判定問題をこのグラフ上で解釈すると、「サイズ $N$ のマッチングが存在するか？」となる。二部グラフの最大マッチングは、蟻本 P.195 やこの記事で述べられているように、最大流問題に帰着することで解くことができる。

高速化

しかし毎回愚直に最大流を求めていると間に合わない。例えば Ford-Fulkerson のアルゴリズムでは、流量の最大値が $N$ なので、計算量は各クエリ $O(N(N+M+Q))$ となる(他のアルゴリズムでもほとんど同様)。

だがよく考えると、一度のクエリで最大流は高々 1 しか増減しない。よって、前に流したフローをそのまま保持しておき、新たに流れたフローだけを求めることで、各クエリ $O(N+M+Q)$ で処理できる。

辺の削除

上の解法では、クエリ毎に辺の追加・削除を行う必要がある。追加は簡単だが、削除は少し考える必要がある。

まず消したい辺にフローが流れていない場合。この場合はその辺の容量を 0 にするだけでよい。

問題なのは消したい辺にフローが流れている場合で、この場合はこの辺を通るフローを消す必要がある。今回は 2 部グラフなので、消したい辺が $uv$ である場合、このフローは常に $s \to u \to v \to g$ という形になっている¹。よって辺 $su, uv, vg$ の流量を 0 にすればよい。

実装例

ac-library の MaxFlow は辺の流量・容量変更ができるので便利。

Run #4856232 < misteer < Solutions | Aizu Online Judge

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


#include <atcoder/maxflow>

namespace ac = atcoder;

#include <iostream>
#include <vector>
#include <map>

void solve() {
    int n, m;
    std::cin >> n >> m;

    int s = n * 2, g = n * 2 + 1;
    ac::mf_graph<int> graph(n * 2 + 2);

    std::vector<bool> exist;                 // 辺が存在するか
    std::map<std::pair<int, int>, int> eid;  // 辺のグラフ中におけるid

    auto add_edge = [&](int u, int v) {
        eid[std::make_pair(u, v)] = graph.add_edge(u, v, 1);
        exist.push_back(true);
    };

    for (int i = 0; i < n; ++i) {
        add_edge(s, i);
        add_edge(i + n, g);
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        add_edge(u, v + n);
    }

    // 初期流量
    int f = graph.flow(s, g);

    int q;
    std::cin >> q;
    while (q--) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;

        if (eid.count({u, v + n})) {
            int i = eid[{u, v + n}];

            if (exist[i]) {
                // 辺iの容量を0にする
                if (graph.get_edge(i).flow == 1) {
                    // 押し戻す
                    --f;
                    graph.change_edge(eid[{s, u}], 1, 0);
                    graph.change_edge(eid[{v + n, g}], 1, 0);
                }
                graph.change_edge(i, 0, 0);

            } else {
                // 辺iの容量を1にする
                graph.change_edge(i, 1, 0);
            }
            exist[i] = !exist[i];

        } else {
            // 新たな辺を追加
            add_edge(u, v + n);
        }

        // 差分だけ流す
        f += graph.flow(s, g);

        std::cout << (f == n ? "Yes" : "No") << "\n";
    }
}

もしもっと長い形をしている場合、流量を増やすことができる。例えば $s \to u' \to v' \to u \to v \to g$ なら、 $s \to u \to v' \to g$ に流すことができる。 ↩︎