我草，终于开始学线性规划对偶了。
抄袭一下 dxm 论文。
定义
首先线性规划是这样一个东西：
令 \(x\) 是 \(1\times n\) 向量，\(A\) 是 \(m\times n\) 矩阵。则上述形式对应了一个，\(n\) 个变量 \(m\) 条约束的线性规划问题。
\(x_i\) 可以是实数，但一定非负。
第一行被称作目标函数，也就是我们要最优化的内容。下面的都是我们的约束。
对偶
我们可以转而去做这样一个问题：
下面这个式子的答案和上面的是一致的。
这个结果其实有很多东西值得我们理清一下：
- 首先我们注意到原问题是可能无解的：而线性规划对偶只在有解的条件下成立。换言之对偶，对判断有无解是没有帮助的，我们往往需要先确认原问题有无解。
- 注意到 \(y\) 是 \(1\times m\) 矩阵。实质上：对偶就是对原问题的每个约束，新建了一个关于它变量（不妨乘坐该限制的对偶变量）。
- 我们很容易写出对偶后的目标函数，但是约束不容易比较快速的写出。按照我的理解：对偶后的问题，每个约束都和原问题中的一个变量 \(x_i\) 相关。不等式右侧很好写，左侧实际上是就是，你考虑原问题的每个约束 \(j\)，如果在这个约束的左侧，\(x_i\) 的系数是 \(p_j\)。那么在对偶后的问题里，\(y_j\)（也就是这个约束的对偶变量）的系数就也是 \(p_j\)。这样就能比较快速地写出对偶后的约束。
等于的情况
常有 \(Ax=b\) 这样的约束，我们当然可以拆成 \(Ax\ge b\) 和 \(Ax\le b\) 来研究，但是还有更简洁的方法。
不妨说，有两个变量 \(x_1,x_2\)，然后我们要求最大化 \(x_1+x_2\)，限制是 \(x_1+x_2= c\)。拆成 \(x_1+x_2\le c\) 和 \(-x_1-x_2\le -c\)。
对偶以后：也就是最小化 \(y_1-y_2\)，然后两条限制长得一摸一样：怎么都是 \(y_1-y_2\ge 1\)？
令 \(Y:=y_1-y_2\) 然后你发现就是最小化 \(Y\)，约束 \(Y\ge 1\)。而且你发现本来 \(y_1,y_2\) 都要求 \(\ge 0\)，但 \(y_1-y_2\) 就无所谓了。
因此碰到等于的约束，我们依旧可以只得出一个对偶变量，并且它自身并不带非负的要求，可以任意取值（当然可能会被其他限制约束到）。
费用流对偶
考虑下列网络流问题：
无源汇最小费用流，可能有负权边。对每个点 \(u\)，要求：它流出的流量减去流入的流量恰好为 \(b_u\)。
首先这个问题怎么费用流解决？我们先把负权边流满建反边，然后跑上下界的做法。如果能说明没有负环，则不用流满负权边，直接跑上下界也可以。我们先假设这个问题是一定有解的。
然后写出线性规划形式：
令 \(z_{u,v}\) 是 \(-f_{u,v}\ge -c_{u,v}\) 的对偶变量，\(p_u\) 是 \(\sum_{v}f_{u,v}-\sum_{v}f_{v,u}=b_u\) 的对偶变量。对偶后得：
这里有一个很重要的技巧：消去多余变量。就是说，假如我们确定了所有的 \(p\)，则因为 \(c\) 是非负的，那么 \(z\) 一定越小越好。而注意到：\(z_{u,v}\ge p_u-p_v-w_{u,v}\)。因此我们可以直接取等号（和 \(0\) 取最大值），然后：
至此，我们其实已经得到了一种机械求解这种最优化问题的方法。当然你需要确保得到的费用流问题一定有解。
例：ZJOI2013 战线规划
令 \(s_i\) 是 \(1\sim i\) 里放置了多少个。约束可以写成 \(s_{r}-s_{l-1}\ge d\) 的形式。
还有 \(s_i\ge s_{i-1}\)，发现也可以写成上面的约束。
代价定义为 \(\sum_{i=1}^{n}b_i(s_{i}-s_{i-1})\)，重写一下也就是 \(\sum_{i=0}^{n}(b_i-b_{i+1})s_i\)，因此可以重定义一下 \(b_i\)，然后变成 \(\sum_{i=0}^{n}b_is_i\)。
注意到我们并不需要令 \(s_0=0\)，反正你的代价是以相邻的 \(s\) 的差的形式定义的。事实上我们想让 \(s_0=0\) 也比较困难。
怎么套用到上面的形式呢？我们只用给约束加一个 \(\infty\) 的权：也就是：
你发现这个式子取反就是上面的形式，直接对着建图跑费用流就行了。
不过这个题比较不牛，费用流板子比较菜会被卡，打不过单纯形。。
例：Aizu2230 How to Create a Good Game
令 \(x_{u,v}\) 是边 \(u\rightarrow v\) 增加的量，而 \(w_{u,v}\) 是原始边权。
再令 \(f_i\) 是新图 \(1\rightarrow i\) 的最长路。原图里 \(1\rightarrow n\) 的最短路为 \(C\)。
则我们写出线性规划形式：
依旧是考虑消去无用变量：假如我们确定了 \(f\)，则 \(x_{u,v}\le f_{v}-f_{u}-w_{u,v}\) 会直接去等号，而且这里不能和 \(0\) 取 \(\max\)，否则意味着此时 \(f_{v}-f_{u}\lt w_{u,v}+(x_{u,v}=0)\)。所以应该把约束改写成 \(f_{v}-f_{u}\ge w_{u,v}\)。
整理一下：
直接建图跑费用流即可，这次随便过了。
另外的一些例题
不能总机械套这个模型吧？
ZJOI2020 序列
虽然有三种操作，但其实从每个位置的视角来看，只有两种操作：一种是 \([l,r]\) 内的全部加，一种是 \([l,r]\) 内指定奇偶性的人加。
首先如果我们只有一操作，那么是 NOIP2018 T1 啊啊：答案直接就是 \(\sum_{i=1}^{n}\max\{0,a_{i}-a_{i-1}\}\)。
然后我们令 \(f_i\) 是位置 \(i\) 有多少次一操作，\(g_i\) 是位置 \(i\) 有多少次二操作，则有：
（以下我们都认为下标在 \([1,n]\) 范围外，就代表 \(0\)。）
注意到 \(g_i=a_i-f_i\)，因此可以消去。得：
到这里我们还无法直接对偶：因为目标函数里有和 \(0\) 取 \(\max\)。
接下来的手法很有启发性：当我们的目标函数里出现了 \(\max\{0,x\}\) 这种东西的时候，我们不妨新建一个变量 \(y \ge x\)，然后因为线性规划自带的 \(y\ge 0\) 的限制，\(\min: y\) 就等价于 \(\min:\max\{0,x\}\)。我们对目标函数里的两个 \(\max\)，新建变量 \(y_i,z_i\)，则：
此时可以直接对偶了，对三条限制分别新建对偶变量 \(X,Y,Z\)：
注意到确定 \(X,Y\) 以后，有 \(Z_i\ge -X_{i}+X_{i+1}+Y_{i}-Y_{i-2}\)。因此 \(Z_i=\max\{0,-X_i+X_{i+1}+Y_i-Y_{i-2}\}\)。
因为这个问题能建出费用流模型，所以可以保证解的整数性，因此 \(X,Y\) 的取值都是 \(0/1\)。
这样：最大化 \(\sum_{i=1}^{n}(a_i-a_{i-2})Y_i-\max\{0,-X_{i}+X_{i+1}+Y_{i}-Y_{i-2}\}\) 就可以直接 dp 了。
时间复杂度 \(O(n)\)。
World Tour Finals 2022 Day1 D. Welcome to Tokyo!
线性规划对偶的好题。但是整数型相关的内容有点无法感受明白啊？
我们直接令 \(a_i\) 是 \(i\) 是否选择 \(0/1\)。然后：
整数规划难以处理，但是我们可以猜测其一定有最优整数解，所以可以直接看作一般的线性规划。
在对偶之间，注意到目标函数有 \(\min\{1,x\}\) 这种形式，运用上面所述的技巧：
对偶：令四条限制的对偶变量分别为 \(X_i,Y_i,Z_i,C\)，得：
四个变量实在是太难以处理：考虑对于每个 \(C\)，提前算出目标函数减去 \(kC\) 的最优解 \(b_C\)。这样对于每个 \(k\)，我们就相当于是查询 \(\min kC+bC\)，容易求出。然后我们考虑 \(C\) 固定的情况。
根据解的整数性以及我们的最优化方向：\(Y_i+Z_i\ge 1\) 可以拆成：\(Y_i\oplus Z_i=1\)。
因此 \(Z_i=1-Y_i\)。所以第一条限制变为：\(X_i-m+\sum_{i\in [l_j,r_j]}Y_j+C\ge 0\)。
这里需要观察到一个贪心性质：最优解一定满足 \(X=0\)：否则我们选出其中的 \(X\) 个 \(Y=0\) 的位置，将他们变成 \(1\)，目标函数显然不会更大。
那么我们的目标函数变成了 \(\min:\sum_{i=1}^{m}Y_i+kC\)，而第一条约束变为了 \(\forall i,m-\sum_{i\in[l_j,r_j]}Y_j\le C\)。
如果一个区间的 \(Y_i=0\)，则我们称这个区间被选中。则我们就是在做这样一个问题：
- 选出尽可能多的区间，使得每个点被覆盖的次数不超过 \(C\)。
那么我们瞬间有很多想法，比如凸性什么的。我们来考虑对于一个固定的 \(C\)，建出网络流模型：
那就是有一条拆点的单向链，限制了每个点被经过了不超过 \(C\) 次，然后我们对于一个区间，连 \(s\rightarrow in(L)\) 和 \(out(R)\rightarrow t\)。跑最大流就是答案。
首先 \(C=1\) 是经典弱智贪心：按照右端点排序考虑每个区间是否能加入即可。
考虑 \(C\rightarrow C+1\) 的时候发生的变换。实际上也就是对每个点的 \(in\rightarrow out\) 之间多新连一条边出来。
那你观察这个新增的连边，就很显然不会出现新的增广路是经过反悔边的。因此我们可以从这个角度来发现答案具有增量性。
也就是我们求出 \(C\) 的时候选中了哪些区间。然后 \(C\rightarrow C+1\) 的时候对剩下的区间继续套那个 \(C=1\) 的贪心就行了。
但其实还有点问题的，就是我们新增了 \(x\) 个区间的话，其实这 \(x\) 个区间也许是能有交的：比如我们有两个区间有交，但是这个交点之前都没被覆盖过，在 \(C\ge 2\) 的时候这就是合法的。
所以考虑修改一下贪心：假设我们当前选的区间是 \([l,r]\)，则先找到最大的 \(p\le r\) 使得 \(p\) 被覆盖了 \(C\) 次，然后找到一个未被使用的，\(r\) 最小的，且 \(l\gt p\) 的区间，选中即可。
时间复杂度 \(O((n+m)\log)\)。