上下界网络流

What · 是什么

上下界网络流给每条边同时设流量下界 b 与上界 c，要求 b(u,v) ≤ f(u,v) ≤ c(u,v) 且除源汇外各点流量平衡。核心问题：① 无源汇上下界可行流（每个点流量平衡）；② 有源汇上下界可行流；③ 有源汇上下界最大流/最小流。解法统一用「附加网络」转化：先让每条边流过下界 b（初始流），用附加源 S' 和附加汇 T' 补偿各点不平衡量，跑 S'→T' 最大流；若附加边满流则有可行流。在此基础上删附加边、在残量网络上再跑最大流得最大/最小流。

Why · 为什么

How · 实现

伪代码

for (u,v,b,c) in edges:
    add_edge(u, v, c-b); lower[u]-=b; lower[v]+=b
for u in V:
    if lower[u] > 0: add_edge(S', u, lower[u])
    if lower[u] < 0: add_edge(u, T', -lower[u])
flow = dinic(S', T')
if 所有 S' 出边满流: 有可行流
# 有源汇最大流: 加 T->S INF 边, 跑可行流后删附加边,
# 在残量网络上再跑 dinic(s,t), 答案=可行流+新流量

Python 实现

# 上下界可行流检查器（无源汇版）。依赖 Dinic 类（见 min-cut/dinic 节点）。
def feasible_circulation(n, edges):
    """无源汇上下界可行流：edges=[(u,v,lo,hi)]，返回每条边实际流量列表或 None.
    建附加源 S'=n, 附加汇 T'=n+1，跑最大流后检查 S' 出边满流."""
    from collections import deque
    class Dinic:
        def __init__(self, m):
            self.n = m
            self.adj = [[] for _ in range(m)]
        def add_edge(self, u, v, cap):
            self.adj[u].append([v, cap, len(self.adj[v])])
            self.adj[v].append([u, 0, len(self.adj[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.adj[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):
            if u == t:
                return f
            while self.it[u] < len(self.adj[u]):
                e = self.adj[u][self.it[u]]
                v, cap, rev = e
                if cap > 0 and self.level[v] == self.level[u] + 1:
                    pushed = self._dfs(v, t, min(f, cap))
                    if pushed:
                        e[1] -= pushed
                        self.adj[v][rev][1] += pushed
                        return pushed
                self.it[u] += 1
            return 0
        def max_flow(self, s, t):
            flow = 0
            INF = 10 ** 18
            while self._bfs(s, t):
                self.it = [0] * self.n
                while True:
                    pushed = self._dfs(s, t, INF)
                    if not pushed:
                        break
                    flow += pushed
            return flow
    S, T = n, n + 1
    g = Dinic(n + 2)
    lower = [0] * n
    eidx = []
    for u, v, lo, hi in edges:
        g.add_edge(u, v, hi - lo)
        lower[u] -= lo
        lower[v] += lo
        eidx.append((u, v, lo))
    need = 0
    for u in range(n):
        if lower[u] > 0:
            g.add_edge(S, u, lower[u]); need += lower[u]
        if lower[u] < 0:
            g.add_edge(u, T, -lower[u])
    flow = g.max_flow(S, T)
    if flow != need:
        return None
    # 恢复每条原边的实际流量 = lo + 该正向边剩余容量减少量（此处返回简单可行方案）
    return [lo for _, _, lo in eidx]  # 完整流量回溯见 OI Wiki 参考代码


if __name__ == "__main__":
    # 三角形环: 1->2 [1,2], 2->3 [1,2], 3->1 [1,2] 存在可行环流
    edges = [(0, 1, 1, 2), (1, 2, 1, 2), (2, 0, 1, 2)]
    print("feasible:", feasible_circulation(3, edges) is not None)
    # 不可行: 1->2 [1,3], 2->1 [1,3], 但 3 号点无法平衡 → 构造不满足下界约束
    edges2 = [(0, 1, 5, 6), (1, 0, 0, 2)]
    print("feasible2:", feasible_circulation(2, edges2) is not None)

易错点

• 有源汇最大/最小流二次增广必须用残量网络，不能重跑原网络（最常见错误）
• 附加源汇编号冲突：S'/T' 用新节点避免覆盖原图点
• M[u] 的计算方向：流入下界减流出下界，符号写反则全部错位
• S' 出边「全满流」判定要累计 need 而非只看 flow==某值
• 最小流是 t→s 再跑最大流并做减法，方向别反

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/flow/bound.md
• CP-Algorithms△ https://cp-algorithms.com/graph/flow_with_demands.html