共享分配最优覆盖算法问询：带负载限制的水源分配问题

这本质是个带容量约束的最大匹配问题，直接用最大流模型就能解决，步骤很清晰：

1. 流网络建模 #

把问题转化为一个有向流网络，节点分为四类：

• 超级源点S：作为所有人群的起点
• 人群节点：每个对应一个待分配的人
• 水源节点：每个对应一个水源
• 超级汇点T：作为所有水源的终点

然后按规则连边：

• 超级源点S到每一个人群节点连一条边，容量设为1（每个人只能被分配一次）
• 每个人群节点到自己可接入的水源节点各连一条边，容量设为1（每人只能选一个水源）
• 每个水源节点到超级汇点T连一条边，容量设为该水源的承载上限n（每个水源最多接n个人）

2. 计算最大流 #

用最大流算法计算这个网络的最大流，最大流的数值就是能覆盖的最多人数，而流的路径对应具体的分配方案：比如S→人群A→水源X→T，就代表把人群A分配给水源X。

常用的算法有：

• Edmonds-Karp算法：基于BFS找增广路，实现简单，适合中小规模的场景
• Dinic算法：用分层图+阻塞流优化，效率更高，适合人群和水源数量较多的大规模场景

3. 实际优化小技巧 #

• 提前筛掉没有任何可接入水源的人群，不用把他们放进模型，减少计算量
• 如果所有水源的承载上限都是n，建模时可以统一设置，不用逐个调整
• 重叠覆盖的水源场景下，模型会自动优先分配，保证整体覆盖人数最多——毕竟最大流算法的核心就是在容量约束下最大化流量（这里的流量就是覆盖人数）

内容的提问来源于stack exchange，提问作者twSoulz