带容量约束有向图中多人源汇通行最小天数的最大流建模求解

核心结论 #

这个问题是典型的带边容量约束的最快流问题，完全可以通过最大流算法求解，工程上最容易实现的方案是「二分答案+时间扩展网络最大流校验」，也可以用逐时间层增量建图增广的方式直接计算，实际运行效率更高。 #

建模实现步骤 #

以通用性最强的二分方案为例，流程如下：

1. 确定二分查找范围
   我们要找的是M个人全部到达汇点的最小天数T：下界取源点1到汇点N的无权最短路径长度（哪怕无拥堵，单人走最快路径也要花这么久），上界取最短路径长度 + M（极端情况单路径每天仅能通行1人，M人排队最多额外花M天）。
2. 针对每个待验证的T，构建时间扩展流网络
   核心是把时间维度拆为独立的网络层，把时序约束转化为流网络的边容量约束：
   • 节点拆分：将原图每个节点u拆为T+1个副本，记为u_0, u_1 ... u_T，u_t表示第t天结束时人员位于节点u的状态。
   • 连边规则：
     • 停留边：对每个节点u、每个时刻t ∈ [0, T-1]，从u_t向u_{t+1}连容量为M的边（总人数仅为M，该容量足够容纳所有选择在节点等候的人员），对应人员在节点停留1天不移动的行为。
     • 通行边：对原图中每条u→v、容量为w的有向边，对每个时刻t ∈ [0, T-1]，从u_t向v_{t+1}连容量为w的边，对应人员花1天通过该边的行为：第t天从u出发，第t+1天抵达v，同时最多通行w人，完全匹配题目给出的边容量、单天通行耗时约束。
   • 源汇配置：新增超级源点S，向原源点的0时刻副本1_0连容量为M的边，对应M个人从第0天的源点出发；新增超级汇点，将原汇点所有时刻的副本N_0, N_1 ... N_T全部向超级汇点连容量为M的边，代表只要在T天内任意时刻到达汇点就算完成通行。
3. 校验逻辑
   对建好的网络跑最大流（这类分层图用Dinic算法效率极高），如果算出的最大流等于M，说明T天足够让所有人抵达汇点，可以尝试更小的T；如果最大流小于M，说明T天无法满足通行需求，需要增大T。二分找到的最小可行T就是答案。

示例匹配验证 #

对应题中3人通行的案例：

• T=1时，网络中仅1_0到3_1的直达边可通汇点，该边容量为1，最大流仅为1，小于总人数3，校验不通过。
• T=2时，除1人走1→3的直达边1天抵达外，剩余2人可走1_0→2_1→3_2的路径，该路径各边容量均为2，刚好容纳2人，总流量达到3，校验通过，因此最小通行天数为2，和示例结果完全一致。

效率优化方案 #

如果不想做二分，也可以从t=0开始逐次新增t时刻的节点层、对应的停留边和通行边，每加完一层就跑一次增广，累计从S到汇点的总流量，直到总流量达到M，此时的t就是最小天数。该方案在总人数M不大时，实际运行效率比二分法更高。

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