线段树模拟费用流：高效解决产品销售利润最大化问题

1. 先搞清楚原题在问什么一个看起来像线性规划的销售模型我第一次看到「产品销售」这四个字的时候第一反应是这不就是个贪心吗每天生产、每天卖卖不掉存起来存起来有成本哪天卖利润最高就哪天卖。后来仔细读题才发现自己把问题想简单了。这个题的核心难点不是“要不要存”而是“库存这个容量无限、时间连续、每一天的成本都不一样”的条件下怎么用数据结构把费用流的增广过程压到 O(n log n)。我先把题意按照比较通俗的方式描述一下。有 n 天第 i 天可以生产一定数量的产品产量上限记为 a_i每生产一单位产品的成本是 c_i。第 i 天市场有一个需求量 b_i每卖出一单位产品能获得收益 p_i。生产出来的产品如果没有当天卖掉可以留到之后的任意一天再卖但是每留一天每一单位产品需要支付一个存储费用 w_i注意这里的 w_i 表示从第 i 天留到第 i1 天的单位存储成本。问最大能获得多少利润。这个模型其实很贴合现实里的库存管理你今天生产多了放在仓库明天卖掉明天又生产后天卖掉。生产成本和售价在不同天不一样存储成本也会随时间变化。题目只要求得到最大利润不需要输出每一天具体生产多少卖多少这就给数据结构优化留下了空间。我第一次拿到这个题的时候脑子里冒出来的就是最小费用最大流。源点往每个生产天连一条容量 a_i、费用 c_i 的边每个销售天往汇点连一条容量 b_i、费用 -p_i 的边因为收益要作为负费用然后第 i 天往第 i1 天连一条容量无限、费用 w_i 的边表示把产品往后存一天。跑一遍最小费用最大流把总费用取负数就是最大利润。这个建图非常直观但是 n 的范围一旦到了十万级别边数就是 O(n) 的每次增广都可能要跑 SPFA 或者 Dijkstra总复杂度根本没法看。哪怕是加了势能优化的最小费用流面对十万级别节点和可能高达百万级别的总流量也会直接暴毙。所以才需要把这张特殊的链状图结构利用起来用线段树去“模拟”费用流增广的过程而不是真的把图建出来。2. 为什么可以模拟费用流这张图的增广路有很强的结构性想要用数据结构替代费用流第一件事就是观察增广路的结构。在这个模型中节点是按照天数从 1 到 n 排列的除了源点和汇点之外每天和相邻天之间只有一条双向链路。费用流每做一次增广本质是在残留网络上找一条从源点到汇点的最短路然后把这条路上的流量增加。因为原图只有一条时间链所以任意一条从源点到汇点的增广路从生产天出发到存储边再到销售天一定是先沿着时间方向走到某个销售天或者先反向走若干个存储边再正向走到销售天。换句话说一次增广对应的是“某一天生产某一天销售”两者之间的时间距离决定了存储费用差距越大额外费用越高。这就是整道题的关键观察虽然看起来是费用流但因为图是一条链每一次增广只需要回答一个问题——在当前剩下的供给和需求中选哪一对“生产天”和“销售天”组合能带来最大的边际利润。这个最大利润等于销售价格减去生产成本再减去这段时间的存储总费用。如果直接把每一天看成点那么任意一对生产日 i 和销售日 ji j连线的费用就是收益p_j - c_i存储成本sum_{ki}^{j-1} w_k需要找到最大收益的一对然后尽量匹配。这个就是一个经典的“老鼠进洞”问题左边有一堆老鼠生产右边有一堆洞销售匹配收益随距离变化还要处理容量。模拟费用流的思路是每次找当前最优的一对把能匹配的量全部匹配掉然后更新相关容量。由于每次匹配可能让原本不优的匹配变得优所以还要支持“反悔”操作。线段树在这里的职责就是维护一个支持区间加、区间最小值/最大值查询、以及快速定位最有价值匹配点的数据结构。3. 线段树维护的信息把“最优匹配”压进树里先约定一些记号免得后面代码说不清楚。设前缀和数组prod_sum[i] 表示前 i 天累计生产能力的剩余总量sell_sum[i] 表示前 i 天累计需求的剩余总量w_pre[i] 表示前 i 天存储费用的前缀和w_pre[i] sum_{k1}^{i} w_k。如果某天还没有被完全匹配我们可以用一个集合来表示当前还能用来生产的日期以及还能用来销售的日期。由于每次匹配必然是“某个生产日在某个销售日之前”所以一条增广路的价值可以表示成value(i, j) (p_j - w_pre[j]) - (c_i - w_pre[i-1])只要 i j这个式子就是销售收益减去生产费用再减去 i 到 j 的存储费用。如果我们把每一天同时拆成两个角色——当它作为生产来源时贡献一个值 A_i c_i - w_pre[i-1]当它作为销售去向时贡献一个值 B_j p_j - w_pre[j]——那么任意 i j 的匹配收益就是 B_j - A_i。这个形式非常漂亮。它把存储费用从距离相关的复杂项变成了只和端点相关的前缀差。原本一个区间上的匹配问题被拆成了两个独立的“标量”问题。于是我们只需要维护两个序列A 序列每个生产天 i 当前的“生产代价”越小越值得生产B 序列每个销售天 j 当前的“销售收益”越大越值得销售每次找最优匹配需要找到一对 i j使 B_j - A_i 最大。朴素想法是枚举 j然后在所有 j 的 i 中找最小的 A_i再维护全局最大值。但是还要支持容量消耗后的更新以及反悔操作所以不能只简单前缀扫。线段树在这里维护的不只是最大值而是要维护四个分量区间内最小的 A_i区间内最大的 B_j区间内“左边生产、右边销售”能获得的最大收益这个最大收益对应的生产位置和销售位置当一个区间的左子区间和右子区间合并时最大匹配收益有三种可能完全在左边完全在右边或者生产在左边、销售在右边。最后一种就是左子区间最小 A 加上右子区间最大 B。这个合并规则非常像经典的“线段树维护最大子段和”只不过把左端和右端换成了 A 和 B。有了这个节点设计我们就可以在树上递归如果当前节点的左儿子内部收益最大就走左儿子如果右儿子内部收益最大就走右儿子如果跨越左右儿子的收益最大就返回左儿子最小 A 的位置和右儿子最大 B 的位置。一次增广就能 O(log n) 找到最优匹配点对。找到了之后剩下的操作就是调整容量和费用这也是线段树能支持区间更新的地方。4. 核心流程与代码骨架区间加如何触达“反悔”边上面说的都是“怎么找最优匹配”真正难的是“匹配完之后怎么更新”。这里的更新不只是把生产和销售的剩余容量减掉还要处理费用流里反向边的逻辑。在裸费用流中每次增广都会在残留网络上添加一条反向边费用为原费用的相反数。这样后续增广就有可能“撤销”之前的匹配让流量重新流动到更优的方案。在模拟费用流里我们同样需要维护这种反悔能力。具体来说如果某一天 i 作为生产来源被使用了一部分我们应该允许它之后被“替换”成另一个生产来源替换的收益变化也要能被数据结构捕捉。这需要通过线段树区间加来调整 A 和 B 序列的值。举个例子假设我们选定了生产天 x 和销售天 y匹配了 flow 单位流量。在费用流里源点到 x 的边剩余容量减少 flowx 到汇点的反向边增加 flow同时 y 到汇点的边减少 flow源点到 y 的反向边增加 flow。对于链上的存储边如果流量从 x 流向 y则中间所有存储边也形成了正向流量反向边上就多出了负费用的“反悔路径”。在所有反悔路径中最有价值的是这样一类当未来某天 z 想生产并销售到更早的某天 t 时可以“挤掉”之前 x 到 y 的部分流量让 x 的产能转而供应 z 的需求而原来的 y 需求由 z 的新生产来满足或者反过来。这种链式替换在最小费用流中体现为一系列区间加操作。具体怎么维护可以这样理解当一个生产位置 i 的容量被消耗了一部分它作为“源”的价值会变化因为它对应的 A_i 不再可取需要把它替换成一个“可用虚拟源”的位置这个虚拟源的价值可能来自未来某天。当我们匹配了 x 到 y对于所有在 x 到 y 之间的天其实相当于增加了一个“负费用的中间通道”这个通道的价值是 -w 的往返效果。用线段树表示就是在某个区间上的 A 或 B 统一加减一个常数。这里需要非常小心因为区间加的对象不是整个序列而是和匹配区间有关的特定范围。我的做法是把费用流增广过程拆成三个阶段找到最优匹配 (x, y)得到收益 val 和流量 flow min(剩余生产容量[x], 剩余销售需求[y])。从生产容量中扣除 flow从销售需求中扣除 flow。对线段树执行若干区间更新把这次匹配对后续选择的影响反映到 A/B 序列中。第 3 步是核心。因为一旦 x 的剩余产能被用掉了如果之后有一个销售天 z 想用 x它其实是在“抢”之前已经分配给 y 的产能这个时候会出现一条新的增广路z 到 x 的反向存储边再走 x 到 y 的原有正向边最终替代原来的匹配。而这条新路径的价值可以通过对 A 或 B 的区间加来等价实现。为了方便统一处理我用线段树维护的是每个位置“作为销售端时还能新增的收益”和“作为生产端时还能节省的费用”。匹配结束后会对区间 [x, y] 内的所有位置做一次区间加加的数值根据 w 的前缀差计算。这个过程一多就需要懒标记支持区间加。下面是这套线段树简化版的核心代码模型我用结构体来描述节点选手在实现时可以按需压缩。struct Node { long long minA; // 区间内最小 A 值 long long maxB; // 区间内最大 B 值 long long best; // 区间内最优匹配收益 int posA; // 最小 A 对应的位置 int posB; // 最大 B 对应的位置 int posBestL; // 最优匹配中生产端位置 int posBestR; // 最优匹配中销售端位置 long long lazyA; // 对 A 序列的懒标记 long long lazyB; // 对 B 序列的懒标记 };合并两个子节点 left 和 right 时大致长这样node.minA min(left.minA, right.minA); node.maxB max(left.maxB, right.maxB); node.best max(left.best, right.best); node.best max(node.best, left.minA right.maxB); if (node.best left.best) { node.posBestL left.posBestL; node.posBestR left.posBestR; } else if (node.best right.best) { node.posBestL right.posBestL; node.posBestR right.posBestR; } else { node.posBestL left.posA; node.posBestR right.posB; }当然实际判断建议用大于号而不是大于等于否则会引入随机性导致匹配不稳定后续调试困难。这里只是演示逻辑。一旦某个区间需要整体加上一个常数只需要同时更新 node.minA、node.best 和 node.lazyA同理 maxB 和 lazyB。尤其是 best 值的更新如果对整个区间内的所有 A_i 同时加 delta那么任意一对匹配收益 B_j - A_i 都会减少 delta所以 best 也要减 delta。同理对 B 整体加 delta 会让 best 增加 delta。这套操作维护好之后每次找最优匹配就是一次全局查询。查询到最优收益如果已经小于等于 0说明再做匹配也无法增加利润直接结束。5. 调题实录我在这个题上踩过的坑这个题看着思路清楚写起来细节多到爆炸。我第一版代码写完跑小数据基本是对的但是一上大数据就出现负收益匹配或者匹配位置错乱。复盘下来有几个坑特别值得记录。第一个坑前缀和的方向搞反。存储费用是从生产天 i 存到销售天 j 之间产生的所以是 sum_{ki}^{j-1} w_k。这个 w 序列的下标容易写错。我一开始把 w_pre 的定义写成了 w_pre[i] sum_{k1}^{i} w_k然后匹配收益用了 p_j - c_i - (w_pre[j] - w_pre[i])这表示的是从第 i1 天存到第 j 天的费用会差一个 w_i。你如果推成 A_i c_i - w_pre[i-1]B_j p_j - w_pre[j]就不会错。建议在草稿纸上多做几组手算尤其是跨越多天的时候。第二个坑反悔操作对应的区间加不是整个 [x, y]。一开始我想省事匹配完后直接把 [x, y] 整段的 A 和 B 都加了一个数结果发现最优匹配会被错误地吸引到已经用完的天上。后来我模拟费用流增广过程发现反悔只影响匹配区间内那些“还有剩余能力”的位置而这些位置在递归更新时并不一定连续。正确做法是在每次匹配后沿着当前匹配端点分别向上递归只对必要子区间做标记而不是对整个 [x, y] 一刀切。想省事的话可以先把 x 和 y 在树上的位置找出来然后对路径上的节点单独处理。第三个坑容量用完后没有及时把对应天从可用集合中踢出去。比如生产天 x 的剩余容量变成了 0但它的 A 值还在线段树里甚至因为懒标记变得更小导致后续匹配又选到它。必须在对 x 更新的时候如果剩余容量为 0就把它对应的 A 设成正无穷把 B 设成负无穷并且把相关位置标记成不可用。这一步漏掉程序会陷入死循环或者算出明显偏大的答案。第四个坑收益和费用都用 long long。这个题 n 上万之后任何一点累积值都可能爆 int。存储费用前缀和、生产费用、销售收益、流量累计全部用 long long 最稳妥。我第一版用 intWA 到怀疑人生后来全部改 long long数据就跑对了。还有一个容易被忽略的细节INF 一定要设得足够大至少大于所有费用绝对值之和否则合并节点时最小 A 和最大 B 会被 INF 污染。第五个技巧用暴力程序对拍。这种数据结构的题最终答案可以用普通费用流或者 O(n^2) 动态规划验证。写一个 n 不超过 50 的暴力版本然后随机生成数据不停对拍。我大概对拍了两万组小数据才把边界问题全部找出来。强烈建议任何写“模拟费用流”题目的选手都这么做不要妄想一遍过。6. 复杂度分析和线段树常数优化严格来说这套算法的复杂度是 O((n m) log n)其中 m 是总增广次数。最坏情况下每次增广可能只匹配一单位流量而总流量可能很大所以如果题目数据构造了极端容量纯模拟费用流可能会退化。但对于原题的数据范围因为每次增广都会让某个生产天或销售天的容量归零所以增广次数不超过生产天数和销售天数之和也就是 O(n)。线段树的节点数量是 4n 或者 2 的幂次扩展建议直接用 4 倍空间简单省事。每次全局查询最优匹配是 O(log n)更新容量和区间加也是 O(log n)而且通常需要执行几次递归更新常数因子大概在 3 到 5 左右。在我的机器上n 100000 的数据一套流程跑下来在 0.2 秒左右算是很稳。常数优化方面有几个点合并操作里尽量避免复杂的 pair 比较直接用四个 int 记录位置。懒标记的 pushdown 只做必需的孩子更新如果 node 是叶子就跳过。全局最优匹配可以单独用一个根节点维护不需要单独写查询函数。如果使用 zkw 线段树或者自底向上线段树速度还能更快但代码会更难读。这种题比赛时最重要的不是极限快而是正确率所以我更推荐朴素递归线段树配上足够的空间。7. 从这道题延伸出去的常见变体“线段树模拟费用流”这个套路绝不只是这一道题能用。只要费用流图是一条链或者退化成序列上的匹配问题都可以用类似思路解决。我做完这道题之后又遇到不少题目本质上都是这个题换了一层皮。比如经典的老鼠进洞模型数轴上有若干个老鼠洞每个洞有容量和收益老鼠只能往一边走要匹配最大收益。把老鼠位置和生产天对应洞位置和销售天对应存储费用换成距离线段树维护的区间最大收益就直接变成了答案。区别只是把 w 序列换成连续坐标差A 和 B 的表达式会变成坐标的一次函数。再比如有库存限制的采购销售问题每天可以买入一定数量卖出一定数量仓库容量有限。有限容量意味着存储边有容量上限这时候线段树里的区间加就不只是加常数还需要维护容量上限带来的“截断”操作。不过核心思路还是找到最优增广路只是每次匹配完还要检查库存容量是否越界稍微麻烦一点。还有一种变体是“树状结构”的存储网络比如产品可以存放在多个仓库仓库之间有运输成本。这时候链状图变成树状图线段树也就不够用了得换成树链剖分或者 LCT 去维护。但如果你理解了这道题的线段树合并逻辑再看那些高级数据结构会发现整个模拟费用流的骨架是完全一样的。我在做这道题的时候最大的感受是费用流并不可怕可怕的是把图的特殊结构藏起来不看。只要发现了链状图的最短路等价于序列上“两端点差值”问题就成功转化成了一个数据结构题。而线段树只是我们用来高效维护这个结构的一个顺手工具罢了。8. 最后分享一个调试小技巧如果你也在努力把这个题调到 AC建议单独写一个 dump 函数把线段树每个节点的 A、B、best 打出来。每次增广后对比暴力费用流每一步的增广路看看是否一致。这个方法能帮你快速定位是合并逻辑写错了还是区间加的范围写错了。另一个小技巧是先实现一个只支持匹配但不支持反悔的贪心版本用来生成部分数据下的答案。你会发现贪心和正确费用流的差别恰好来自反悔操作这样就能单独验证反悔逻辑是否正确。我当初就是靠这一步一点点把区间加的范围修正过来的。这道题确实有一定难度但一旦你吃透了“模拟费用流数据结构维护增广路”的核心思想再看类似的题目就会觉得套路非常清晰。希望这篇记录能帮到正在肝这个题的你。