Grid and Tokens [AtCoder Beginner Contest 205 F]

https://atcoder.jp/contests/abc205/tasks/abc205_f

前提知識

• 最大流

解説

https://atcoder.jp/contests/abc205/submissions/23457322

今回の問題は最大流問題に帰着できる。
パッと見て類題を思い出して、選択肢を考えていくと最大流で解法が思いつける。
見たことが無いと解くのは難しい。

DPでも解けそうな感じもするが、選択順を固定することができないので、ちょっと難しそう。
後は、行と列にそれぞれ1つずつしか置けないということもあってマッチング問題っぽく見え、
フローかな…という考察ルートもあるかもしれない。
この辺は頑張るしかない…

以降は、最大流は分かっているものとする。

最大流のグラフの作り方

以下のような感じでグラフを作る

• 頂点は以下の6種類
  • 始点 st
  • 占有されている列を表す頂点 x1, x2, ..., xW
  • 駒を表す頂点1, p1, p2, ..., pN
  • 駒を表す頂点2, w1, w2, ..., wN
  • 占有されている行を表す頂点 y1, y2, ..., yH
  • 終点gl
• 以下のように辺を張る
  • 始点からどの列に駒が置かれているかを表現するのに st -> x? にコスト1の辺を張る
  • どの駒がどの列を占有しているかを表現するのに x? -> p? にコスト1の辺を張る（この時、置ける所だけ辺を張る）
  • 駒は1度しか選択できないので、駒を表す頂点を倍加して1度だけ選択されていることを保証するのに、 pa -> wa にコスト1の辺を張る
  • どの駒がどの行を占有しているかを表現するのに w? -> y? にコスト1の辺を張る（この時、置ける所だけ辺を張る）
  • 始点からどの行に駒が置かれているかを表現するのに y? -> gl にコスト1の辺を張る

これでstからglに最大流を流した時の流量が答えとなる。
駒は1度しか選択できないので、頂点を倍加する所がポイントとなる。

int H, W, N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> N;

    MaxFlow<int> mf(W + N + N + H + 2);

    int st = W + N + N + H;
    int gl = st + 1;

    rep(x, 0, W) mf.add_edge(st, x, 1);
    rep(i, 0, N) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        A--; B--;
        rep(y, A, C) rep(x, B, D) {
            mf.add_edge(x, W + i, 1);
            mf.add_edge(W + N + i, W + N + N + y, 1);
        }
        mf.add_edge(W + i, W + N + i, 1);
    }
    rep(y, 0, H) mf.add_edge(W + N + N + y, gl, 1);

    int ans = mf.maxflow(st, gl);
    cout << ans << endl;
}