Day 128-Q5 — 下限付き最大流（Lower Bound Flow）

2026-08-20 赤色 Master / Phase 8+ ★★★★★★★★★ 超始点・超終点の追加で下限付き循環流を通常の最大流に帰着させる

問題

$N$頂点$M$辺の有向グラフが与えられる。各辺$i$は$(u_i,v_i,lo_i,hi_i)$で表され、流量$f_i$は$lo_i\le f_i\le hi_i$を満たす必要がある。全頂点で流入量=流出量（循環流）となるように全辺の制約を満たす流量割り当てが存在するか判定し、存在するなら一例を出力せよ。

入力形式

N M
u_1 v_1 lo_1 hi_1
...
u_M v_M lo_M hi_M

制約

$1 \le N \le 500$
$1 \le M \le 2000$
$0 \le lo_i \le hi_i \le 10^4$
実行可能解が複数ある場合どれでもよい

入出力例

入力例1

2 2
1 2 1 3
2 1 1 2

出力例1

1
1

辺1,2ともに流量1で両頂点の流入=流出=1が成立し、下限・上限も満たす。

入力例2

2 1
1 2 1 1

出力例2

-1

辺1本だけでは循環流としての流入=流出が絶対に成立しない。

概念図

超始点SS・超終点TTへの帰着 SS u v TT excess[u]<0 の場合 excess[v]>0 の場合 容量 hi-lo SS→TTの最大流=total_demandなら下限付き循環流は実行可能

ヒント（段階的開示）

ヒント1（方向性）

通常の最大流（Dinic法）は下限0・上限cの辺しか扱えない。下限$lo>0$の制約は「流量=lo+自由な追加分」に分解し、lo分をあらかじめ頂点の需給に押し付けることで通常の最大流問題に変換する。

ヒント2（アプローチ）

各辺$(u,v,lo,hi)$を容量$hi-lo$の辺として置き換え、excess[v]+=lo、excess[u]-=loを記録する。excess>0の頂点はTTへ、excess<0の頂点はSSから辺を張り、SS-TTの最大流がSSから出る容量合計と一致すれば実行可能。

ヒント3（誘導） 
ref = add_edge(u, v, hi - lo)  # 変換後の辺
# SS-TT最大流を流した後
remaining_cap = graph[fr][ei][1]
actual_flow = hi - remaining_cap

模範解答 (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, fr, to, cap):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        self.graph[to].append([fr, 0, len(self.graph[fr]) - 1])
        return (fr, len(self.graph[fr]) - 1)

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

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

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


def solve():
    sys.setrecursionlimit(1 << 20)
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    SS = n + 1
    TT = n + 2
    mf = MaxFlow(n + 3)

    excess = [0] * (n + 1)
    edge_info = []

    for _ in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        lo = int(data[idx]); idx += 1
        hi = int(data[idx]); idx += 1
        ref = mf.add_edge(u, v, hi - lo)
        edge_info.append((ref, lo, hi))
        excess[v] += lo
        excess[u] -= lo

    total_demand = 0
    for node in range(1, n + 1):
        if excess[node] > 0:
            mf.add_edge(SS, node, excess[node])
            total_demand += excess[node]
        elif excess[node] < 0:
            mf.add_edge(node, TT, -excess[node])

    flow = mf.max_flow(SS, TT)

    if flow != total_demand:
        print(-1)
        return

    out = []
    for (fr, ei), lo, hi in edge_info:
        remaining = mf.graph[fr][ei][1]
        actual = hi - remaining
        out.append(str(actual))

    print('\n'.join(out))


solve()

Step-by-Step 解説

1下限を頂点の過不足に押し付ける変換
各辺で必ずloだけ流すと仮定すると、v側にlo分の流入、u側にlo分の流出が「タダで」発生する。これをexcessとして記録し、辺自体は残りの自由度hi-loとして扱う。
2超始点・超終点による帳尻合わせ
excess>0（供給過多）はnode→TT、excess<0（需要）はSS→nodeに辺を張る。
3実行可能性の判定
SS-TTの最大流がtotal_demandと一致すれば、全ての過不足を自由度の範囲内で吸収できたことになり実行可能。
4元の流量の復元
変換後の辺の残余容量remainingからactual = hi - remainingで元の流量を復元する。
5計算量
頂点数N+2、辺数M+O(N)程度でDinic法により制約下で十分高速に動作する。

よくあるミス

ミス原因正しい書き方
実行可能性判定を不正確な条件で行う判定条件の理解不足SSから出る辺の容量合計と実際の流量が完全一致するかで判定する
元の流量復元でloを足し忘れる変換後容量と元流量の対応関係の混同actual = hi - remainingで正しく復元する
逆辺の容量を答えとして誤って出力する正引き辺と逆辺の混同add_edgeが返す(fr, edge_index)を保存し正引きの辺を参照する
s-t間フローと誤解しSS,TT以外に始点終点を扱う問題設定の誤解本問題は純粋な循環流なのでSS,TT以外は不要

次のステップ

  • 発展: 「sからtへ少なくともD流したい」下限付きs-tフローは、t→sに容量∞の辺を追加して循環流問題に変換できる
  • 次回予告（新Dayセット）: セントロイド分解・Gomory-Huツリーなど木/フロー系の応用を予定

自己評価

自分の回答

気づき・メモ