Day 102-Q3 | 下限付き最大流の実行可能性判定（Lower-Bound Feasible Flow）

問題

$N$頂点$M$辺の有向グラフが与えられる。各辺$i$には下限$\text{low}_i$と上限$\text{high}_i$（$0\le\text{low}_i\le\text{high}_i$）が指定されている。すべての頂点で流入量と流出量が等しくなる（湧き出し・吸い込みのない循環流である）ように各辺$i$に流量$f_i$（$\text{low}_i\le f_i\le\text{high}_i$）を割り当てられるかを判定せよ。可能なら`Yes`、不可能なら`No`を出力する。

各辺$(u,v,\text{low},\text{high})$を「容量$\text{high}-\text{low}$の辺」に置き換え、下限分の強制流入・流出を仮想ソース$SS$・仮想シンク$TT$で補うことで、実行可能性を通常の$s$-$t$最大流判定に帰着できる古典的な変換テクニック。

入力形式

N M
u_1 v_1 low_1 high_1
:
u_M v_M low_M high_M

制約

$2 \le N \le 50$

$1 \le M \le 100$

$0 \le \text{low}_i \le \text{high}_i \le 100$

頂点1-indexed、$u_i\ne v_i$、多重辺あり得る

入出力例

入力例1

出力例1

Yes

三角形の各辺に流量1を流せば全頂点で流入=流出=1となり、下限1・上限2の範囲にも収まる。実行可能。

入力例2

3 2
1 2 2 3
2 3 1 1

出力例2

No

頂点1は少なくとも流量2を流出しなければならないが、頂点1へ流入する辺が1本もないため条件を満たせない。実行不可能。

概念図

ヒント（段階的開示）

ヒント1: 方向性

「下限がなければ普通の最大流の話」という直感は正しいが、下限があると「各辺に最低これだけは流さなければならない」という強制力が生まれる。この強制分を先に「もう流れたもの」として天引きしておき、残りの自由度（$\text{high}-\text{low}$）だけを通常の最大流として扱えないか、という発想がスタート地点。

ヒント2: アプローチ

各辺$(u,v,\text{low},\text{high})$について容量$\text{high}-\text{low}$の辺$u\to v$を新しく作る。下限分を強制的に流したとみなすと頂点$v$には$\text{low}$の流入超過、頂点$u$には$\text{low}$の流出超過が生じる。各頂点$x$について$d[x]=(\text{xに入る下限の総和})-(\text{xから出る下限の総和})$を計算し、$d[x]>0$なら仮想ソース$SS$から$x$へ容量$d[x]$の辺を、$d[x]<0$なら$x$から仮想シンク$TT$へ容量$-d[x]$の辺を張る。$SS$から$TT$への最大流が$\sum_{x:d[x]>0}d[x]$に一致すれば実行可能。

ヒント3: 誘導（コード骨格）

SS, TT = N, N + 1
mf = MaxFlow(N + 2)
d = [0] * N
for (u, v, lo, hi) in edges:
    mf.add_edge(u, v, hi - lo)
    d[v] += lo
    d[u] -= lo

need = 0
for x in range(N):
    if d[x] > 0:
        mf.add_edge(SS, x, d[x])
        need += d[x]
    elif d[x] < 0:
        mf.add_edge(x, TT, -d[x])

flow = mf.max_flow(SS, TT)
print("Yes" if flow == need else "No")

「$SS$から出る辺の容量総和 = 各頂点で不足している下限流入量の総和」であり、これがすべて満たされて初めて全頂点の流量保存則が成立する。

模範解答 (Python)

import sys
from collections import deque


class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u, v, cap):
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, rev in self.graph[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0

    def dfs(self, u, t, f, it):
        if u == t:
            return f
        while it[u] < len(self.graph[u]):
            v, cap, rev = self.graph[u][it[u]]
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, cap), it)
                if d > 0:
                    self.graph[u][it[u]][1] -= d
                    self.graph[v][rev][1] += d
                    return d
            it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'), it)
                if f == 0:
                    break
                flow += f
        return flow


def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    SS, TT = N, N + 1
    mf = MaxFlow(N + 2)
    d = [0] * N

    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        lo = int(data[idx]); idx += 1
        hi = int(data[idx]); idx += 1
        mf.add_edge(u, v, hi - lo)
        d[v] += lo
        d[u] -= lo

    need = 0
    for x in range(N):
        if d[x] > 0:
            mf.add_edge(SS, x, d[x])
            need += d[x]
        elif d[x] < 0:
            mf.add_edge(x, TT, -d[x])

    flow = mf.max_flow(SS, TT)
    print("Yes" if flow == need else "No")


solve()

計算量: $O(V^2 E)$（Dinic法、$N,M$ともに小さいので余裕）。

Step-by-Step 解説

1下限分を「すでに流れた」ものとして天引き
各辺を「容量$\text{high}-\text{low}$の自由な辺」として扱い直す。

2各頂点の下限収支$d[x]$を計算
$d[v]{+}{=}\text{low}$（$v$への強制流入）、$d[u]{-}{=}\text{low}$（$u$からの強制流出）。

3仮想ソース・シンクで不均衡を補う
$d[x]>0$なら$SS$から補給、$d[x]<0$なら$TT$へ排出する辺を張り、通常の$s$-$t$最大流問題に変換する。

4最大流を計算し飽和判定
$SS\to TT$の最大流が`need`と一致すれば実行可能、一致しなければ不可能。

よくあるミス

ミス	原因	正しい書き方
下限をそのまま辺容量として扱う	「自由に流せる分」と「強制分」を混同する	辺容量は必ず$\text{high}-\text{low}$にし、下限は$d[x]$の集計だけに使う
$SS,TT$を作らず元の$S,T$だけで最大流を取る	循環流問題と通常の$s$-$t$フロー問題を混同する	循環流の場合は必ず仮想ノード$SS,TT$を新設する
最大流の値だけを見て「流れればYes」と誤判定	判定条件が「`need`ちょうどに一致するか」であることを見落とす	必ず`flow==need`で厳密に比較する
多重辺の管理をまとめてしまう	各辺は独立した下限・上限制約を持つ	辺ごとに`add_edge`を独立して呼び出す

次のステップ

発展: 指定されたソース$S$・シンク$T$がある「下限付き$s$-$t$最大流」（$T\to S$に容量$\infty$の辺を追加してから同じ変換を適用し、その後$S\to T$の残余最大流を追加で流す2段階アルゴリズム）
発展: 下限付き最小費用循環流（各辺にコストも付き、実行可能な中で総コスト最小の流れを求める）
次回予告: Dirichlet's Hyperbola Method（約数関数の総和・大きな$N$に対する$O(\sqrt N)$高速計算）

自己評価

完全理解おおむね理解要復習

Day 102-Q3 — 下限付き最大流の実行可能性判定（Lower-Bound Feasible Flow）

問題