燃やす埋める問題（最大フロー最小カット問題）について整理する [演習編]

はじめに

前回の記事では、燃やす埋める問題（最小カット）について、理論の整理をしていきました。今回は演習問題を解いていきます。

ちなみに前回の記事はこちらです。
https://zenn.dev/kiwamachan/articles/37a2c646f82c7d

演習問題1

ARC085-E問題 MUL

https://atcoder.jp/contests/arc085/tasks/arc085_c

宝石 $i$ の各々について「割る」または「割らない」の選択があります。これを有向グラフで表すと下記のようになります。pythonは 0-indexed なので、宝石の数が $N$ 個のときは、頂点 $0$ を s(source) 頂点 $N+1$ を t(sink) に設定することができます。

宝石 $i$ を割ると報酬はありませんが、割らずに残すと $a_i$ 円の報酬があります。 $a_i$ は負の場合があり、その場合には反対にお金を払う必要がありますので、正負で扱いを変える必要があります。
分かりやすくするために、$a_i$ の絶対値を $A$ （$>0$）で表すと

$a_i$ の正負	宝石を割るとき	宝石を割らないとき
正	$0$ 円	$+A$ 円
負	$0$ 円	$-A$ 円

最小カットを考えるときには、報酬は全てマイナスで考える必要があるので、無条件で貰える金額を設定して、報酬をマイナスの値に換算します。

$a_i$ の正負	宝石を割るとき	宝石を割らないとき	無条件で貰える金額
正	$-A$ 円	$0$ 円	$+A$ 円
負	$0$ 円	$-A$ 円	$0$ 円

倍数の宝石も一緒に割ってしまう条件は、例えば「宝石2」を割ったときには「宝石4」「宝石6」も割ってしまいます。宝石2、宝石4について考えると「宝石2を割る」という選択と「宝石4を割らない」という選択が両立しないように（カットが成立しないように）「宝石2」と「宝石4」の間に、コスト無限大の有向辺を設定します。4→2の向きにパスがあれば「宝石2を割る」と「宝石4を割らない」をカットしても、s (source) から t (sink)　への流れはカットできません。

つまり条件をまとめると、宝石1へ [2, 3, 4, 5, 6] から、宝石2へ [4, 6] から、宝石3へ [6] から、有効パスをつないてあげれば良いです。

一般化すると、宝石 $k$ へは　$k×2$、 $k×3$、 $k×4$、・・・から有向辺をつなげば良いです。

実装コード

from collections import deque,defaultdict
N = int(input())
a = list(map(int,input().split()))
INF = 10**18
Val = 0
s,t = 0, N+1
graph = [defaultdict(int) for _ in range(t+1)]

$a_i$ の正負で場合分けをして、有向辺のコストを決めていきます。Valには、無条件で貰える報酬をためていきます。倍数の宝石を同時に割ってしまう条件設定は、無限大コストの有向辺をつくることで実装します。

for i in range(N):
    if a[i] > 0:
        Val += a[i]
        graph[0][i+1] = a[i]
    else:
        graph[i+1][N+1] = -a[i]

for i in range(1,N+1):
    for j in range(i*2,N+1,i):
        graph[j][i] = INF

最大フローを求める関数を考えます。
手順としては、(1) 幅優先探索(BFS)で level に到達順を記録していき、(2) 深さ優先探索(DFS)で s (source) から t (sink)　へ到達する有向パスがあれば、フローを流します。(1)(2)を繰り返して最大フローを求めたら、無条件で貰っていた報酬(Val)から減算することで、解答が得られます。

def max_flow(graph,s,t):
    ret = 0
    # breadth first search
    while True:
        level = [-1]*(t+1)
        level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for u in graph[v]:
                if level[u] < 0 and graph[v][u] > 0:
                    level[u] = level[v] + 1
                    q.append(u)

        visited = [set() for _ in range(t+1)]

        def DFS(x,flow):
            if x == t:
                return flow

            for y in graph[x]:
                if graph[x][y] > 0 and level[x] < level[y] and y not in visited[x]:
                    visited[x].add(y)
                    f = DFS(y, min(flow,graph[x][y]))
                    if f > 0:
                        graph[x][y] -= f
                        graph[y][x] += f
                        return f
            return 0
        
        if level[t] < 0:
            return ret

        while True:
            df = DFS(0,INF)
            if df > 0:
                ret += df
            else:
                break

ans = Val - max_flow(graph,s,t)
print(ans)

演習問題2

典型90問-040 Get More Money

https://atcoder.jp/contests/typical90/tasks/typical90_an

問題文は少し複雑ですが、各家について「入らない」または「入る」の選択肢があるので、最大フロー最小カット問題に置き換えて考えることができます。

家の中にあるお金を前金で受け取ってしまい、家に入らなかったら返却すると考えると、各選択におけるコストは、

家に入らない場合	家に入る場合	無条件で貰える金額
$-A_i$ 円	$-W$ 円	$A_i$ 円

となります。
鍵の条件については、例えば「家3」の鍵が2つあって、「家1」「家2」にあった場合は、「家3に入る」という選択と「家1に入らない」という選択の両立は不可能、「家3に入る」という選択と「家2に入らない」という選択の両立は不可能となります。したがって、これらの選択肢の両立がNGとなるように（これらの選択によるカットでは、s-t がカットされないように）、家3→家1、家3→家2 に無限大の重みを持つ有向辺を設定します。

つまり、家 $X$ の鍵が、家 $Y$ にあった場合には、$X→Y$ へ有向辺（無限大の重み）を設定すれば良いことになります。

実装コード

前問と違うのは、graphの設定のところまでです。

from collections import deque, defaultdict
N,W = map(int,input().split())
A = list(map(int,input().split()))
INF = 10**18
Val = 0
s,t = 0, N+1
graph = [defaultdict(int) for _ in range(t+1)]

for i in range(N):
    Val += A[i]
    graph[0][i+1] = A[i]
    graph[i+1][N+1] = W

for i in range(1,N+1):
    k = list(map(int,input().split()))
    for j in range(k[0]):
        graph[k[j+1]][i] = INF

これ以降は前問と同じで良いです。

def max_flow(graph,s,t):
# 前問と同じコードなので省略

ans = Val - max_flow(graph,s,t)
print(ans)

演習問題3

ABC193-F問題 Zebraness

https://atcoder.jp/contests/abc193/tasks/abc193_f

問題文では、しまうま度は隣り合うマスの色が異なる場合に $+1$ となりますが、その条件下では最小カット問題として扱えませんので $i+j$ が奇数のマスの白黒を反転させて、隣り合うマスの色が同じ場合に $+1$ となると考えます。

グリッドの斜めマスの指定

さらに最小カットは、減点のシチュエーションの方が考えやすいため、初期スコアとして $12$ 点 $2N(N-1)$ を与えて、隣り合うマスの色が異なる場合に $-1$ とします。

各マスについて「B」または「W」の選択があるので、マス番号を $i×N+j+1$ と決めて、各マス番号 $n$ のマスについて「B」を選択するときは $s→n$ の辺をカットし「W」を選択するときは $n→t$ の辺をカットします。始めから「B」となっているマスは「W」側のみ辺を張り、始めが「W」となっているマスは「B」側のみ辺を張るようにします。残した辺がさらにカットされないように、これらの辺の重みは無限大とします。「？」のマスからは、両サイドに辺を張ります。

隣り合うマスの色が同じ場合に $+1$ のペナルティを与えるには、隣り合うマス同士を重み $1$ の辺でつないでおけば良いです。こうすれば「B」「W」が異なるときは、マスの間の辺をカットしないと s→t のパスを切れないので、必然的にペナルティの $-1$ が与えられることになります。

実装コード

「?」の頂点から、s(source)、t(sink)につないだ辺は、カットしてもペナルティはないので、重みの設定が $0$ となります。つまり、最大フローを求めるときには、存在しないのと同じになります。そのためgraphをつくるときには、「?」の頂点については、考える必要がありません。

from collections import deque, defaultdict
N = int(input())
c = [list(input()) for _ in range(N)]
INF = 10**18
Val = 2*N*(N-1)
s,t = 0, N**2+1
graph = [defaultdict(int) for _ in range(t+1)]

for i in range(N):
    for j in range(N):
        x = i*N+j+1
        if (i+j)%2 == 1:
            if c[i][j] == "B":
                graph[s][x] = INF
            elif c[i][j] == "W":
                graph[x][t] = INF
        else:
            if c[i][j] == "W":
                graph[s][x] = INF
            elif c[i][j] == "B":
                graph[x][t] = INF
        
        if i > 0: graph[x][x-N] = 1
        if j > 0: graph[x][x-1] = 1
        if i < N-1: graph[x][x+N] = 1
        if j < N-1: graph[x][x+1] = 1

ここまでのgraph設定が違うだけで、これ以降は前問と同じで良いです。

def max_flow(graph,s,t):
# 前問と同じコードなので省略

ans = Val - max_flow(graph,s,t)
print(ans)

振り返り（実装の工夫）

始めの2問（ARC085E, 典型問題40）は、max_flow関数に特別な工夫をしなくてもAC(Accepted)にできたのですが、3問目のABC193Fは、max_flowを工夫する前はTLE(Time Limit Exceeded)になりました。

＜実装の工夫1＞
始めはgraphの設定をリスト型にしていましたが、defaultdictを用いて辞書型にした方がメモリ消費が少なく高速になりました。

# 始めの設定
graph = [[0]*(t+1) for _ in range(t+1)]
# こっちの方が高速だった
graph = [defaultdict(int) for _ in range(t+1)]

＜実装の工夫2＞
visitedというsetのリストの設定を行い、同じ辺の評価を繰り返さないように設定することで、高速化することができました。

visited = [set() for _ in range(t+1)]