带权差分约束系统

feecle6418 · 2022-01-02 16:39:13 · 个人记录

最大化 \sum c_ia_i，其中有限制 c_y\le c_x+z，c_i=k，c_i\ge 0：使用上下界网络流解决。

• c_i=k$ 的限制：连边 $(S\to i,\infty,k),(i\to T,\infty,-k)
• 最后，对于 a_i：若 a_i\ge 0，连边 (i\to T,[a_i,a_i],0)（强制满流）；若 a_i<0，连边 (S\to i,[-a_i,-a_i],0)（强制满流）（这里和正常思维反了，因为对偶之后 a_x 会被移项）
• 还需要 (x\to T,\infty,0) 平衡流量
• 在这个图中跑有上下界的最小费用可行流
• 如果题目性质保证了最大流是满流，则可以不强制满流，直接跑最小费用最大流即可
• 无解判断：
• 图中有能到的负环。
• 能从 S 到 T 流 \infty 的负权流量。
• 答案为正无穷的判断：
• 没有可行流。

这个是能够输出方案的（用 2016 论文里那个 互松弛定理 建差分约束系统）。但是更一般的形式（dxm 论文里的）我不会输出方案。