AtCoder ARC 074 F - Lotus Leaves (黄色, 800 点)

見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある...

問題へのリンク

問題概要

の二次元グリッドが与えられる。各マスは

• 'S' のマス：カエルがいる
• 'T' のマス：カエルがそこにいきたい
• 'o' のマス：葉っぱがある
• '.' のマス：水 (このマス上には行けない)

という 4 つの属性がある。特に S, T は葉っぱマスでもある。カエルは「同じ行」または「同じ列」にある葉マスを自由に行き来することができる。

カエルが S から T へとたどり着けなくするために、いくつかの葉っぱを取り除きたい。その最小個数を求めよ。

制約

• 

考えたこと

とりあえず葉っぱを頂点に対応させたグラフの最小カットが真っ先に思い浮かぶ。しかしちょっといろいろ工夫が必要である。愚直には

• 葉に対応させた各頂点について、四方八方の同じ列の葉と、容量 INF の辺で結ぶ

としたグラフで、vertex-connectivity を求めれば OK。つまり、各頂点に 1 の容量のあるグラフでの最小カットを求めるということになる。頂点に容量制約のあるグラフを扱うこと自体は難しくない。その頂点 v を、v-in と v-out に分裂させれば OK。

問題は、このままだと として、頂点数 、辺数が となってしまうことだ。辺数が だけあっては、おそらく間に合わない。

dense な状態を、スーパーノードを用意して sparse に

こういう状況を、大昔、なにかの TCO 予選で解いたことがあった気がする。

• 各行の葉は、どの 2 つも互いに容量 INF の辺で結ばれている

という状態だ。これに対してスーパーノード p を付け加えて、

• その行の各頂点 v に対して、v から p への容量 INF の辺と、p から v への容量 INF の辺を結ぶ

という風にしても結果は変わらない。が、これによって辺数のオーダーが下がって となる。これなら間に合う。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// edge class (for network-flow)
template<class FLOWTYPE> struct Edge {
    int rev, from, to;
    FLOWTYPE cap, icap;
    Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap));
    }
};

template<class FLOWTYPE> struct Dinic {
    const FLOWTYPE INF = 1<<30; // to be set
    vector<int> level, iter;

    Dinic() { }
    void dibfs(Graph<FLOWTYPE> &G, int s) {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int i = 0; i < G[v].size(); ++i) {
                Edge<FLOWTYPE> &e = G[v][i];
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    
    FLOWTYPE didfs(Graph<FLOWTYPE> &G, int v, int t, FLOWTYPE f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < G[v].size(); ++i) {
            Edge<FLOWTYPE> &e = G[v][i], &re = G.redge(e);
            if (level[v] < level[e.to] && e.cap > 0) {
                FLOWTYPE d = didfs(G, e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    re.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    FLOWTYPE solve(Graph<FLOWTYPE> &G, int s, int t) {
        level.assign((int)G.size(), -1); iter.assign((int)G.size(), 0);
        FLOWTYPE res = 0;
        while (true) {
            dibfs(G, s);
            if (level[t] < 0) return res;
            for (int i = 0; i < (int)iter.size(); ++i) iter[i] = 0;
            FLOWTYPE flow = 0;
            while ((flow = didfs(G, s, t, INF)) > 0) {
                res += flow;
            }
        }
    }
};
const long long INF = 1<<29;

int main () {
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    auto id = [&](int i, int j) { return i * W + j; };
    
    int s, t;
    Graph<long long> G(H*W*2 + H + W);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (fi[i][j] == 'S') s = id(i, j) + H*W;
            else if (fi[i][j] == 'T') t = id(i, j);
            if (fi[i][j] != '.') G.addedge(id(i, j), id(i, j) + H*W, 1);
        }
    }
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (fi[i][j] == '.') continue;
            G.addedge(id(i, j) + H*W, i + H*W*2, INF);
            G.addedge(i + H*W*2, id(i, j), INF);
        }
    }
    for (int j = 0; j < W; ++j) {
        for (int i = 0; i < H; ++i) {
            if (fi[i][j] == '.') continue;
            G.addedge(id(i, j) + H*W, j + H*W*2 + H, INF);
            G.addedge(j + H*W*2 + H, id(i, j), INF);
        }
    }

    //COUT(G);COUT(s);COUT(t);
    
    Dinic<long long> di;
    auto res = di.solve(G, s, t);

    if (res < INF) cout << res << endl;
    else cout << -1 << endl;
}