不知道是不是对的啊，有没有大爷来看一下啊/kel

因为是第一次证明这种东西，所以写的可能麻烦点了/kk

---

这个问题很难建出最小费用最大路的模型以证明返回贪心的正确性

现在重新建立一个费用流模型，与以往的模型不同的是费用的计算方式：

对于每条边有流量上限 $f$ 以及一个费用计算函数 $c$，当流量为 $i$ 的时候该边的费用为 $c(i)$．

以这个模型建出本题的图：图中仅有源点 $S$，汇点 $T$ 以及一个限制用的 $T'$．对于每个关卡，从 $S$ 向 $T'$ 连一条流量上限为 $2$，$c(0)=0,c(1)=a,c(2)=b$ 的边，$T'$ 向 $T$ 连一条流量上限为 $w$，$c(i)=0$ 的边。求其最小费用最大流即为答案。

现在，需要解决两个问题：

---

一：既然模拟费用流对应着每次贪心流费用最小的增广路并建反向边，首先要证明这张图这样暴力增广能求出最优解。

回顾 SSP 算法的证明，首先先明确一点，当一条边流量为 $k$ 时，在其上多流一个流量的费用是 $c(k+1)-c(k)$．然后考虑直接套用 SSP 算法的证明：

设流量为 $i$ 的时候最小费用为 $f_i$。最初的网络上没有负圈（关于此模型，负环的判定是，以每条边多流一个流量所造成的费用差为边权，即每条边 $c$ 在这个流量处的差分）。

假设用 SSP 算法求出的 $f_i$ 是最小费用，我们在 $f_i$ 的基础上，找到一条最短的增广路，从而求出 $f_{i+1}$。这时 $f_{i+1}-f_i$ 是这条最短增广路的长度。

假设存在更小的 $f_{i+1}$，设它为 $f'_{i+1}$．因为 $f_{i+1}-f_i$ 已经是最短增广路了，所以 $f'_{i+1}-f_i$ 一定对应一个经过至少一个负圈的增广路。

这时候矛盾就出现了：既然存在一条经过至少一个负圈的增广路，那么 就不是最小费用了。因为只要给这个负圈添加流量，就可以在不增加 $s$ 流出的流量的前提下，使 $f_i$ 对应的费用更小。

实际上就是把 SSP 的算法中边权的定义换了一下，因为证明中并没有要求边权的特殊性质（在原最小费用最大流模型中，边权是固定的值即为费用，在新模型中边权变成了一个关于流量的函数即为费用函数的差分）。

---

二：既然这个模型暴力增广是正确的，那么只需要针对这个题建出的图，将增广路种类数缩短到有限种中即可完成模拟费用流，也就是让其可能的增广决策只有有限种。

首先初始图中不存在负环，所以可以直接套用上述模型。

可以不走反向边，直接流到汇点。对应两种贪心策略：

• 将 0 个星变成 1 个星；
• 将 1 个星变成 2 个星。

对于走反向边的增广路，结论是其只会走长度为 $3$ 的增广路，并且第一条和第三条是同一条边。

令 $x$ 和 $x'$ 分别代表关卡 $x$ 的正向边和反向边，其边权记做 $w_x$ 和 $w_{x'}$。

首先，不存在一条来自不同关卡的反向边 $u'$ 和正向边 $v$，满足 $|w_u'|>w_v$，如果存在的话，则增广路流 $u$ 这条边的时候流 $v$ 是更优的，与每次找最短路的策略所矛盾。

所以走正向边时，必须要满足以下条件之一：

• 是路径中的第一条边（还未存在反向边）；
• 非第一条边，那么一定是走完一条反向边 $u'$ 之后的一条边：
  • 是路径中第二次走这条边（这个边权是在增广路过程中新加进来的）；
  • 如果不是路径中第二次走这条正向边 $v$，若 $u=v$，相当于在这个关卡的边上来回走了一次，没有用；如果 $u\neq v$，则不满足引理，故不存在这种情况。

所以正向边只可能有两条，并且来自同一关卡。

故走反向边的增广路对应以下两种贪心策略：

• 将一个关卡的 1 个星变成 0 个星，另一个关卡 0 个星变成 2 个星；
• 将一个关卡的 2 个星变成 1 个星，另一个关卡 0 个星变成 2 个星；

至此，反悔贪心的正确性得到证明。