二部マッチング問題とは

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

このような問題は例えば

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

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

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

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

問題例1

D - Maxflow

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

実装例

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

$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$の場合である。

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

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

実装例

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))