ARC074 F問題：Lotus Leaves

問題. Lotus Leaves

縦 行，横 列の長方形の池がある．池にはいくつか蓮の葉が浮かんでおり，同じ行または列にある葉へは双方向に移動可能である．カエルが葉 から へ移動しようとしている．葉 以外の葉を取り除くことによって から へ到達できなくなるかを判定し，到達不可能ならば取り除く葉の最小値を求めよ．

制約：

解法. 最小カット問題

としたとき，頂点集合を として， にある蓮の葉に対して，容量1の辺 を加える．また，'S' と 'T' がそれぞれ にあるとき，容量無限大の辺 を加える．答えは 最小カットである．'S' と 'T' が同じ行または列にあるときどのようにしても到達可能となる．このとき，無限大を適切な値に設定しないとオーバーフローするので注意が必要．

計算時間： 　(Dinic法を使用)

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

template<typename Weight>
struct Dinic {
    struct Edge {
        int src, dst, rev;
        Weight weight;
        Edge(int f, int t, Weight cap, int rev = 0) :
            src(f), dst(t), rev(rev), weight(cap) {}
    };

    int n;
    vector<vector<Edge>> adj;
    const Weight INF;

    Dinic(int _n, Weight inf = numeric_limits<Weight>::max() / 10)
        : n(_n), adj(n), INF(inf) {}

    void add_edge(const int src, const int dst, const Weight cap) {
        adj[src].emplace_back(Edge(src, dst, cap, adj[dst].size()));
        adj[dst].emplace_back(Edge(dst, src, 0, adj[src].size() - 1));
    }

    Weight MaximumFlow(const int s, const int t) {
        Weight flow = 0;
        while(true) {
            vector<int> level(n, -1), iter(n);
            Bfs(s, level);
            if(level[t] == -1) break;
            for (Weight f = 0; (f = Dfs(s, t, INF, level, iter)) > 0; )
                flow += f;
        }
        return flow;
    }

    void Bfs(const int s, vector<int> &level){
        queue<int> que;
        for (level[s] = 0, que.push(s); !que.empty(); ) {
            const int v = que.front(); que.pop();
            for (const auto &e : adj[v])
                if(0 < e.weight && level[e.dst] == -1){
                    level[e.dst] = level[v] + 1;
                    que.push(e.dst);
                }
        }
    }

    Weight Dfs(int v, int t, Weight flow, vector<int> &level, vector<int> &iter) {
        if(v == t) return flow;
        for ( ; iter[v] < adj[v].size(); ++iter[v]) {
            Edge &e = adj[v][iter[v]];

            if(0 < e.weight && level[v] < level[e.dst]){
                Weight d = Dfs(e.dst, t, min(flow, e.weight), level, iter);
                if(0 < d){
                    e.weight -= d;
                    adj[e.dst][e.rev].weight += d;
                    return d;
                }
            }
        }
        return 0;
    }
};

int Solve() {
    int h, w;
    cin >> h >> w;

    vector<string> hasu(h);
    for (auto &&x : hasu) cin >> x;

    const int s = h + w, t = h + w + 1;
    Dinic<int> g(h + w + 2);

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (hasu[i][j] == 'o') {
                g.add_edge(i, j + h, 1);
                g.add_edge(j + h, i, 1);
            }
            else if (hasu[i][j] == 'S') {
                g.add_edge(s, i, g.INF);
                g.add_edge(s, j + h, g.INF);
            }
            else if (hasu[i][j] == 'T') {
                g.add_edge(i, t, g.INF);
                g.add_edge(j + h, t, g.INF);
            }
        }
    }

    int res = g.MaximumFlow(s, t);
    return (res < g.INF ? res : -1);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cout << Solve() << endl;

    return 0;
}

まとめ

巨人の肩の上に立つような問題

参考文献

• ABC #062 / ARC #074 Editorial @sugim48