二部マッチング問題とは？

# 二部マッチング問題とは

二部マッチング問題とは、2つのカテゴリ含まれるノード間に辺がある場合に、最大何辺(何ペア)取れるかを考える問題である。

```mermaid
graph TD
    A1((A1)):::red --> B1((B1)):::blue
    A1((A1)):::red --> B2((B2)):::blue
    A2((A2)):::red --> B2((B2)):::blue
    A2((A2)):::red --> B3((B3)):::blue
    A3((A3)):::red --> B1((B1)):::blue
    A3((A3)):::red --> B3((B3)):::blue

    classDef red fill:#ffcccc,stroke:#ff0000,stroke-width:2px;
    classDef blue fill:#ccccff,stroke:#0000ff,stroke-width:2px;
```

このような問題は例えば

- 男女のペアマッチング問題
- グリッドの盤面上でタテヨコ被らないように駒を置く問題(タテとヨコの行番号を各1つしかとらないことを考える)

などに応用することができる。

この問題を解くとき、**最大流問題**として落とし込むことが重要である。

```mermaid
graph TD
    S((S)):::source --> |1| A1((A1)):::red
    S((S)):::source --> |1| A2((A2)):::red
    S((S)):::source --> |1| A3((A3)):::red
    
    A1((A1)):::red -->|1| B1((B1)):::blue
    A1((A1)):::red -->|1| B2((B2)):::blue
    A2((A2)):::red -->|1| B2((B2)):::blue
    A2((A2)):::red -->|1| B3((B3)):::blue
    A3((A3)):::red -->|1| B1((B1)):::blue
    A3((A3)):::red -->|1| B3((B3)):::blue
    
    B1((B1)):::blue --> |1| T((T)):::sink
    B2((B2)):::blue --> |1| T((T)):::sink
    B3((B3)):::blue --> |1| T((T)):::sink

    classDef source fill:#ffffcc,stroke:#ffcc00,stroke-width:2px;
    classDef sink fill:#ffccff,stroke:#ff00ff,stroke-width:2px;
    classDef red fill:#ffcccc,stroke:#ff0000,stroke-width:2px;
    classDef blue fill:#ccccff,stroke:#0000ff,stroke-width:2px;
```

最大流問題とは、上図においてSからTに向かって水を流したときに、各辺のキャパシティ以下しか水が流れないという条件の下でTまでどのくらいの量の水を流すことができるのかという問題である。

## 問題例1

[D - Maxflow](https://atcoder.jp/contests/practice2/tasks/practice2_d)

>$N$行$M$列のマス目があります．上から$i$行目，左から$j$番目のマス目をマス$(i,j)$と呼ぶことにします．

> 現在，それぞれのマスは，障害物が置かれているか，空であるかのどちらかの状態です．これらの状態は，文字列$S_1, S_2, ..., S_N$によって表され，マス$(i,j)$の状態は，$S_{i,j} = $`#` なら障害物が置かれていること，$S_{i,j} = $`.` なら空であることを意味します．

> これらのマスに，$1\times2$ の大きさのタイルを置きたいです．タイルは，縦または横に連続する 2 つの空マスの上に置くことができます．タイルを盤面からはみ出すように置くことや，障害物や他のタイルがすでに置かれているマスにタイルを重ねることは禁止されています．最大でいくつのタイルを置くことができるか求めてください．また，実際にその最大値を達成する方法を 1 つ示してください．

例えば以下のように$3 \times 3$のマスを市松模様のように色分けすることを考える。黒は`B`、白は`W`、障害物が置かれている場所は`#`で表現されている。

```
B#B
WBW
BWB
```

$1\times 2$の大きさのタイルを置くとき、必ず白いマスとそれに隣接する黒いマスに置かれることになる。そのため、この隣接するマス同士に辺を張り、最大何ペア取得することができるかを考えればよい。
したがって、このとき考える最大流問題を図にすると以下のようになる。

```mermaid
graph TD
  style B1 fill:#000,stroke:#000,stroke-width:2px,color:#fff
  style B3 fill:#000,stroke:#000,stroke-width:2px,color:#fff
  style B5 fill:#000,stroke:#000,stroke-width:2px,color:#fff
  style B7 fill:#000,stroke:#000,stroke-width:2px,color:#fff
  style B9 fill:#000,stroke:#000,stroke-width:2px,color:#fff

  style W2 fill:#999,stroke:#999,stroke-width:2px,color:#000
  style W4 fill:#fff,stroke:#000,stroke-width:2px
  style W6 fill:#fff,stroke:#000,stroke-width:2px
  style W8 fill:#fff,stroke:#000,stroke-width:2px

  source --> B1
  source --> B3
  source --> B5
  source --> B7
  source --> B9

  B1 --> W2
  B1 --> W4

  B3 --> W2
  B3 --> W6

  B5 --> W4
  B5 --> W6
  B5 --> W8

  B7 --> W6
  B7 --> W8

  B9 --> W8

  W2 --> target
  W4 --> target
  W6 --> target
  W8 --> target

```

### 実装例


```python
from atcoder.maxflow import MFGraph

N,M = list(map(int,input().split()))
matrix = [list(input()) for i in range(N)]
graph = MFGraph(N*M+2)
start = N*M
target = N*M+1
for i in range(N):
    for j in range(M):
        if matrix[i][j] == '#':
            continue
        if (i+j)%2==0:
            graph.add_edge(start,i*M+j,1)
            if i>0:
                graph.add_edge(i*M+j,(i-1)*M+j,1)
            if i<N-1:
                graph.add_edge(i*M+j,(i+1)*M+j,1)
            if j>0:
                graph.add_edge(i*M+j,i*M+(j-1),1)
            if j<M-1:
                graph.add_edge(i*M+j,i*M+(j+1),1)
        else:
            graph.add_edge(i*M+j,target,1)
        
# 流す
# このとき流量が各edgeのflowに収まる
# 返り値が最大流量
print(graph.flow(start,target))

edges = graph.edges()

for e in edges:
    #print(e) #Edge(src=1, dst=10, cap=1, flow=1)
    if e.src==start or e.dst==target or e.flow==0:
        continue
    i0 = e.src // M
    j0 = e.src % M
    i1 = e.dst // M
    j1 = e.dst % M
    if i0==i1:
        if j0 > j1:
            matrix[i0][j0] = '<'
            matrix[i1][j1] = '>'
        else:
            matrix[i0][j0] = '>'
            matrix[i1][j1] = '<'
    else:
        if i0 > i1:
            matrix[i0][j0] = '^'
            matrix[i1][j1] = 'v'
        else:
            matrix[i0][j0] = 'v'
            matrix[i1][j1] = '^'

for i in range(N):
    print(''.join(matrix[i]))
```


## 問題例2

[F - Grid and Tokens](https://atcoder.jp/contests/abc205/tasks/abc205_f)

> $H$ 行 $W$ 列のグリッドがあり、上から $r$ 行目、左から $c$ 列目のマスを $(r, c)$ と表します。

> $N$ 個の駒があり、$i \, (1 \leq i \leq N)$ 個目の駒に対しては

> - $\( A_i \leq r \leq C_i \) $かつ $\( B_i \leq c \leq D_i \) $を満たすいずれか一つのマス $(r, c)$ に置く
> - 置かない

> のいずれかを選択することができます。ここで、二つの駒が同じ行や同じ列に存在するような置き方をすることはできません。

> 最大で何個の駒を置くことができるでしょうか？

この問題の最大流問題を図示したものが以下である。ただし$H=3,W=3,N=2$の場合である。

```mermaid
graph TD;
    style source fill:#f9f,stroke:#333,stroke-width:4px;
    style target fill:#f9f,stroke:#333,stroke-width:4px;

    source --> H1[H1]
    source --> H2[H2]
    source --> H3[H3]
    
    style H1 fill:#ffcccc,stroke:#333,stroke-width:2px;
    style H2 fill:#ffcccc,stroke:#333,stroke-width:2px;
    style H3 fill:#ffcccc,stroke:#333,stroke-width:2px;

    H1 --> N1_1[N1_1]
    H2 --> N1_1[N1_1]
    H2 --> N2_1[N2_1]
    H3 --> N2_1[N2_1]

    style N1_1 fill:#ccffcc,stroke:#333,stroke-width:2px;
    style N1_2 fill:#ccffcc,stroke:#333,stroke-width:2px;

    N1_1 --> N1_2[N1_2]
    N2_1 --> N2_2[N2_2]

    style N2_1 fill:#ccccff,stroke:#333,stroke-width:2px;
    style N2_2 fill:#ccccff,stroke:#333,stroke-width:2px;

    N1_2 --> W1[W1]
    N1_2 --> W2[W2]
    N2_2 --> W2[W2]
    N2_2 --> W3[W3]

    style W1 fill:#ffffcc,stroke:#333,stroke-width:2px;
    style W2 fill:#ffffcc,stroke:#333,stroke-width:2px;
    style W3 fill:#ffffcc,stroke:#333,stroke-width:2px;

    W1 --> target
    W2 --> target
    W3 --> target
```

$H_1$や$W_2$などのノードはそれぞれ行と列に対応しており、**駒を1つ置くことを条件に合うような`h`と`w`を1つずつ選ぶことと読み替えることで**各行各列にそれぞれ1つしか駒を置けないようにしている。

しかしこの2種類のノードだけでは各コマに条件付けがされていることを考慮することができない。間に`N1_1`や`N1_2`のノードを挟んでいるのは、各コマでコマの置ける範囲が制限されていることを表現している。



### 実装例

```python
from atcoder.maxflow import MFGraph

H,W,N = map(int,input().split())
graph = MFGraph(H+W+2*N+2)
start = H+W+2*N
target = H+W+2*N+1

# タテヨコ1列ずつしか選べないようにする
for h in range(H):
    graph.add_edge(start,h,1)
    
for w in range(W):
    graph.add_edge(H+w,target,1)

# i個目の駒の置き方に関する条件付け
for i in range(N):
    src = H+W+2*i
    dst = H+W+2*i+1
    graph.add_edge(src,dst,1)
    a,b,c,d = map(int,input().split())
    for h in range(a-1,c):
        graph.add_edge(h,src,1)
    for w in range(b-1,d):
        graph.add_edge(dst,H+w,1)
    
print(graph.flow(start,target))
```