AtCoder ABC285-G Tatami 最小流量制限付き最大流 の解法をそれとなく理解する - 類題ALPC-Dからのアプローチ

https://atcoder.jp/contests/abc285/tasks/abc285_g

類題であるAtCoder Library Practice Contest の D - Maxflowの解き方を解説してこの問題を解きます。

# ALPC D: MaxFlow
https://atcoder.jp/contests/practice2/tasks/practice2_d

説明を簡便にするため１次元で考えます。<font color=red>（注意：１次元の場合は端から貪欲に敷き詰めていけば最適解ですが、元の問題＝２次元では貪欲には解けません）</font>
この問題は隣接する`.`(空)２マスを使って1x2マスのタイルを最大で何枚敷き詰められるかを求めたいです。各マスを市松模様(`白と灰色`)と考えると、2マスのタイルは必ず`隣接した灰色と白１マスずつ`に敷くことになることが分かります。これを図に示します。
<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/fc23ebe1-21a4-16bc-2caa-e7590e6d6bb4.png width=100%>
入力として左のタイルが与えられたとき、左下のクリーム色のようにタイルを敷くことが出来ます。これは右に示す通り、灰色と白のペアのタイルを２枚に敷いていることに他なりません。

この問題は最大流として解くことが出来ます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/c0478c3a-6ef6-6703-384e-03e09cefdcac.png)
辺の張り方は上記図のようになります。辺の張り方は`#でない灰色部分にタイルを置き、どのむきに置くかを決める`とイメージすると良いです。ソース(s)からは#でない灰色に対して流量1を流すことが出来ます。#でない白部分のタイルはシンク(t)に対して流量1を流せます。そして、各灰色は隣接する白に流量1を流せます。上記図の右ではオレンジの線でフローが流れていますがこれは左側の灰色でなくて、右側の灰色から白に流れていても良いです。つまり、
- 各マスを偶奇などで市松模様として捉える。
- "#"のマスを使わないようにしながら、ソースから灰色に、白からシンクに、灰色から隣接する白(左右)にそれぞれ流量1の辺を張る
- ソースからシンクに流せる最大流が最大値
- 方法の復元(>, <, ^, v)は各辺を復元すればよい
とすればよく、この解き方はそのまま２次元（や３次元）に拡張することができます。市松模様や灰色に置くという考え方をそのまま、上下のノードにも辺を貼ってやればよいです。
<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/88478330-a9c1-c7b6-13f5-3a94413afe85.png width=50%>

# ABC285-G Tatami
説明を簡便にするため、同様に１次元で考えます。この問題では上記考察の大半を流用できます。入力は`.#`であったものが`12?`となっていますが、"1"は"#"と同じに扱ってよいです。"?"を"1"か"2"のいずれとして扱えば良いかがこの問題の難しいところです。
<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/fc7a6395-a5bd-2d5e-1c58-fcec9c03a734.png width=80%>

例えば上図の入力を考えると、真ん中の`???`は`><.`や`.><`のように1x2のタイルを引いても良いですし`...`のようにタイルを敷かなくとも条件を満たします。

２つの例を見ます。
<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/32142355-e643-6d88-7766-0d5207682d93.png width=100%>
左図は隣接する"2"にタイルを敷き、他の`?`は"1"として扱えば条件を満たします。対して右図は条件を満たせません。2つの"2"には必ず1x2のタイルを敷かないとなりませんがそれぞれ隣接した"1"を1つ持つので、真ん中の"."にタイルを置きたいですがどちらか一方しか置けないためです。このように"2"のマスを意識しながら"?"をどう扱えば良いかを考える必要があります。

これは最小流量制限付き最大流で解くことが出来ます。通常の最大流は各辺に流せる流量制限だけを設定しますが、最小流量制限付き最大流は各辺に流さなければならない最小流量を指定できます。そして、その最低流量を満たした上での最大流を求めること、あるいは、そのような条件を満たせないかの判定ができます。先ほどの例をグラフにして示します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/2471c1d0-33fd-e353-10f6-2e8691cea874.png)
先ほどと同様に各マスを市松模様として扱って辺を貼ります。"1"のマスは"#"として扱うため辺を張りません。1x2のタイルに注目すると"?"のマスは置かれてもおかれなくても良いので最小流量制限はmin0とします。"2"のマスには最小流量制限をmin1とします。これはソースから"2"である灰色、"2"である白からシンクの辺に制限を設けます。"2"である灰色から"?"である白、および、灰色から"2"である白、の辺はmin0で良いです。

このような辺を張った上図にある最下層の図に注目します。左図はオレンジの線に流量1のフローが流れ、すべてのminが満たされます。対して右図は右２つの灰色に1ずつのフローを流したいですが、真ん中の白が流量1までしか流せないためこれを満たすことが出来ないので条件を満たせないことが分かります。

ALPC-Dと同じく、この解き方はそのまま２次元（や３次元）に拡張することができます。

# 実装
両者とも上記の通りに実装を行います。
ALPC-DはACLを使うと簡単です。最小流量制限付き最大流は
[最小流量制限付き最大流 - snukeさんのblog](https://snuke.hatenablog.com/entry/2016/07/10/043918)に詳しいです。実装は[Luzhiled's memo](最小流量制限付き最大流)からコピーさせていただきました。

- Tatami
https://atcoder.jp/contests/abc285/submissions/38135670

- ALPC-D
https://atcoder.jp/contests/practice2/submissions/38124052

<details><summary>参考: ALPC-D</summary><div>

```C++
int main() {
    int oh, ow; cin >> oh >> ow;
    char maze[oh][ow];
    REP(h, oh){
        REP(w, ow) {
            cin >> maze[h][w];
        }
    }
    int n = oh * ow ;
    int nodes = oh * ow; // source
    int nodet = nodes + 1; //
    // create s -> node, node -> t
    mf_graph<int> mf(n + 1 + 1);
    REP(h, oh){
        REP(w, ow) {
            if(maze[h][w] == '#') continue;
            auto node = h * ow + w;
            if( ((h + w) % 2)== 0) mf.add_edge(nodes, node, 1);
            else mf.add_edge(node, nodet, 1);
        }
    }
    vector<pair<int, int>> delta = {{-1, 0}, {0, -1}, {0, 1}, { 1, 0}};
    // create node - node
    REP(h, oh){
        REP(w, ow) {
            auto node = h * ow + w;
            if( ((h + w) % 2) != 0) continue; // whiteはいらない
            for(auto &[dh, dw]: delta){
                auto nh = h + dh;
                auto nw = w + dw;
                if(!(0 <= nh && nh < oh)) continue;
                if(!(0 <= nw && nw < ow)) continue;
                if(maze[nh][nw] == '#') continue;
                auto nxt = nh * ow + nw;
                mf.add_edge(node, nxt, 1);
            }
        }
    }
    // DRAW!
    auto ans = mf.flow(nodes, nodet);
    for(auto &edge: mf.edges()){
        //cout << "!";
        if(edge.from == nodes) continue;
        if(edge.to == nodet) continue;
        if(edge.flow == 0) continue;
 
        auto w = edge.from % ow;
        auto h = edge.from / ow;
        //cout << "!a" << h << w<< edge.from << " "<< edge.to << "\n";
        if(edge.from == edge.to+1){ // <-
            maze[h][w-1] = '>';
            maze[h][w] = '<';
        }
        if(edge.to == edge.from+1){
            maze[h][w] = '>';
            maze[h][w+1] = '<';
        }
 
        if(edge.to - edge.from == ow){
            maze[h][w] = 'v';
            maze[h+1][w] = '^';
        }
        if(edge.from - edge.to == ow){
            maze[h][w] = '^';
            maze[h-1][w] = 'v';
        }
 
    }
    cout << ans << "\n";
    REP(h, oh) {
        REP(w, ow) cout << maze[h][w];
        cout << "\n";
    }
}
```
</div></details>

上記折り畳みのコードはALPC-Dのものですが、Tatamiのコードと差分を取ると辺を張る部分しか変更していないことが分かります。(復元がなかったりはしますが)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/30938/a8d92466-5e9a-3e1d-a2fa-d04a5bbfb355.png)