有向网络最大流求解:同源出边流量相等约束的实现问题
满足源节点出边流量均等约束的最大流实现方案
核心思路
你原来的「先分配流量再回溯调整」的思路复杂度高且容易出现冲突,更稳定的实现方式是把约束内置到求解流程中,通过二分搜索+普通最大流验证的方式求解,不需要事后调整流量:
- 假设你要求的是仅源节点的所有出边流量相等,记源节点出度为
k,每条出边流量为f,那么源节点总流出流量为k*f - 我们只需要找到最大的可行
f,即可得到满足约束的最大流
具体实现步骤
- 先确定f的取值范围:
- 下限为0
- 上限为
min(源节点所有出边的容量, 无约束普通最大流总流量 / k)
- 对f做二分搜索:
- 每次取中间值
mid_f作为候选的单条源出边流量 - 构造临时残留网络:将源节点的所有出边容量临时限制为
mid_f,其余边容量不变 - 在临时网络上跑普通最大流算法,得到当前最大流
max_f - 如果
max_f == k * mid_f,说明这个f是可行的,尝试搜索更大的f;否则缩小f的搜索范围
- 每次取中间值
- 最终得到的最大可行f对应的总流量
k*f就是符合约束的最大流,此时所有源出边流量均为f,自动满足约束
现有代码修改建议
你当前的find_augmenting_routes函数存在两个问题:
- 没有判断边的残留容量,会搜索到不可行的路径
- 没有加访问标记,遇到环会陷入无限递归
修正后的增广路径搜索+Ford-Fulkerson实现示例
class WeightedEdge: def __init__(self, from_vertex, to_vertex, capacity): self.tail = from_vertex self.head = to_vertex self.capacity = capacity # 新增剩余流量属性 self.flow = 0 class Graph: def __init__(self, vertices, edges, capacities): self.vertices = vertices self.edges = [WeightedEdge(edges[i][0], edges[i][1], capacities[i]) for i in range(len(edges))] # 新增反向边存储,用于残留网络更新 self.adj = {v: [] for v in vertices} for e in self.edges: rev_e = WeightedEdge(e.head, e.tail, 0) e.rev = rev_e rev_e.rev = e self.adj[e.tail].append(e) self.adj[e.head].append(rev_e) # 重置所有边流量,用于每次二分验证 def reset_flow(self): for e in self.edges: e.flow = 0 e.rev.flow = 0 # 标准Ford-Fulkerson实现 def ford_fulkerson(graph, source, sink): max_flow = 0 while True: # DFS找增广路径 parent = {} visited = set() def dfs(v): if v == sink: return True visited.add(v) for e in graph.adj[v]: if e.head not in visited and e.capacity - e.flow > 0: parent[e.head] = e if dfs(e.head): return True return False if not dfs(source): break # 计算增广量 min_flow = float('inf') v = sink while v != source: e = parent[v] min_flow = min(min_flow, e.capacity - e.flow) v = e.tail # 更新残留网络 v = sink while v != source: e = parent[v] e.flow += min_flow e.rev.flow -= min_flow v = e.tail max_flow += min_flow return max_flow # 最终的带约束最大流求解函数 def max_equal_split_flow(graph, source, sink): # 拿到源节点所有出边 source_out_edges = [e for e in graph.edges if e.tail == source] k = len(source_out_edges) if k == 0: return 0 # 求无约束最大流作为上限参考 graph.reset_flow() unconstrained_max = ford_fulkerson(graph, source, sink) low = 0 high = min(min(e.capacity for e in source_out_edges), unconstrained_max // k) best_f = 0 # 二分搜索 while low <= high: mid = (low + high) // 2 # 临时修改源出边容量 original_caps = [e.capacity for e in source_out_edges] for e in source_out_edges: e.capacity = mid graph.reset_flow() current_max = ford_fulkerson(graph, source, sink) # 恢复原容量 for i, e in enumerate(source_out_edges): e.capacity = original_caps[i] if current_max == k * mid: best_f = mid low = mid + 1 else: high = mid - 1 # 返回总流量和每条源出边的流量 return best_f * k, best_f
扩展场景
如果你的约束是所有节点的出边都要满足流量均等,只需要对二分逻辑做扩展:对每个中间节点,根据其入流量和出度计算每条出边的允许流量,更新对应边的容量上限后再做最大流验证即可。
内容的提问来源于stack exchange,提问作者Micheal Nestor
相关产品推荐
相关产品推荐

