关于 线性规划对偶定理 的一些问题。
经典的引入
Alice开了一个拖拉机厂，她进购了一批铁，轮胎和发动机，这些东西可以用来生产拖拉机，挖掘机和三蹦子(为什么三蹦子的发动机和轮胎和拖拉机是一样的啊¿)，每个都需要一定量的原料。显然，Alice希望自己的利润尽量大。
Bob有一个魔法工厂，他用铁，轮胎和发动机批量生产黄金，于是Bob想买走Alice的这批原料。两个人都是绝顶聪明的，于是Bob知道如果想买下来，自己出的钱必须足够多，不少于Alice生产这些东西所能得到的收益。更进一步，Bob买足够制造一个拖拉机的原料，那么他出的价钱必须不低于一个拖拉机的价钱，挖掘机和三蹦子也是一样的。
于是两个人的目标看起来好像是相反的 : Alice希望提高价格，而Bob希望降低价格。容易感觉到最后两个人将会达成一致，也就是Alice的最大利润将等于Bob的最小出价。感性理解一下这就是线性规划对偶定理。
下面我们需要形式化地表述这个问题。假设Alice这边生产一个拖拉机需要\(a_{1,1},a_{1,2},a_{1,3}\)个单位的铁，轮胎和发动机，挖掘机，三蹦子是\(a_{2,...},a_{3,...}\)，它们构成了矩阵\(A\)。设三种原料分别有\(b_1,b_2,b_3\)个，它们构成了向量\(b\)。设三种产品分别生产\(x_1,x_2,x_3\)个，售价分别是\(c_1,c_2,c_3\)，它们构成了向量\(x,c\)。那么Alice就希望求
\[\max_x c^T x\\ Ax\leq b\\ x\geq 0\]设Bob对三种原料的开价分别是\(y_1,y_2,y_3\)，那么Bob希望求
\[\min_x b^T y\\ A^T y\geq c\\ y\geq 0\]。线性规划对偶定理的内容，就是这两个线性规划的最优解的值相等。
要证明这个?我不会，如果你想知道可以自己查一查（
然后呢
如何写一个线性规划的对偶
如果你想要记住这个式子，这是很简单的。但是如果你想直接用出来，就比较困难，一个方法是你可以认为线性规划对偶就是把变量变成约束，把约束变成变量，符号取反(\(\min\)变成\(\max\)，\(\leq\)变成\(\geq\))，交换\(b,c\)。注意对偶之前把不等号统一。
具体一点?
约束对偶成的变量，在目标函数中的系数是这个约束右边的常数。
变量对偶成的约束，如果这个变量\(x\)出现在某个约束\(A\)中，那么\(x\)对偶出的约束会包含\(A\)对偶出的变量，这个变量系数等于\(x\)在\(A\)中的系数。这个约束右边的常数是这个变量原来在目标函数中的系数。
一个笑话
可能会帮助你理解对偶线性规划?
试看看!例题1.6
二分图最大权匹配的对偶。
线性规划是
\[\max \sum_{u,v}w_{u,v}f_{u,v}\\ \sum_v f_{u,v}\leq 1\text{ for }u\\ \sum_u f_{u,v}\leq 1\text{ for }v\]当然\(f\)需要是正的。设第一个约束对偶成的变量是\(y_u\)，第二个是\(z_v\)，对偶这个我们得到
\[\min \sum_u y_u+\sum_v z_v\\ y_u+z_v\geq w_{u,v}\]呃这是怎么对偶出来的……考虑到每条边只会出现在两个端点的约束中，系数都是\(1\)，然后你就可以大致理解这个式子。
这个对偶问题看起来像是……km。\(y,z\)就是km中的顶标。
试看看!例题1.7
费用流的对偶。这个很有用。
这里我们对偶最大费用循环流，它可以使用最大费用最大流解决(充满正权边再建立虚源汇调整)，并且很多题目可以转化成这个。
\[\max \sum w_{u,v}f_{u,v}\\ \sum_{v}f_{v,u}-\sum_{v}f_{u,v}=0\text{ for }u\\ f_{u,v}\leq c_{u,v}\]首先考虑第一个限制，也就是那个等式的对偶。等式会被拆成两个不等式，看起来是\(a\leq b,-a\leq -b\)。这两个约束会对偶成两个变量\(y,y^\prime\)，它们的系数分别是\(b,-b\)，于是在对偶线性规划中就有一项\(b(y-y^\prime)\)。原来的变量会对偶成约束，这相当于是有一个变量\(y^{\prime\prime}\)可以取任意实数而系数是\(b\)。同时这两个约束对对偶后的约束们是没有影响的，因为正负系数恰好消掉了。
设第一个限制对偶成变量\(h_u\)，第二个限制对偶成变量\(y_{u,v}\)，考虑每个\(f_{u,v}\)对偶成的约束，每个\(f_{u,v}\)只在端点和容量的约束中出现，想一想我们得到
\[\min \sum c_{u,v}y_{u,v}\\ y_{u,v}+h_u-h_v\geq w_{u,v}\\ y_{u,v}\geq 0\]注意到这里面\(h\)出现的时候总是两个的差，所以\(h\)能不能取负其实不重要。
同时注意到我们要求的是最小值，而\(y\)的约束的不等号都是\(\geq\)，所以这个要么无界要么所有\(y\)都取下界\(\max(w_{u,v}-h_u+h_v,0)\)，而根据对偶问题的意义它不可能无界。
于是我们可以扔掉\(y\)，所以问题就是求\(\min \sum c_{u,v}\max(w_{u,v}-h_u+h_v,0)\)，其中\(c,w\)是给定的，\(c\)非负而\(w\)没有限制，\(h\)是实数变量。
根据全幺模矩阵的知识，我们知道这样的问题如果参数都是整数，得到的答案也是整数。
试看看!练习1.8
钦定了超额流的最大费用循环流的对偶，也就是说我们钦定\(e_u\)是\(u\)的入流减去出流。
可以推出它的对偶是求\(\min\left(\sum c_{u,v}\max(w_{u,v}-h_u+h_v,0)+\sum e_uh_u\right)\)，跟上面的过程一致，可以留作练习。
这个东西也很好用最短增广路跑，但是我不知道怎么直接用循环流比如capacity scaling跑（
稍微切几个
线性规划对偶定理有啥用?
最直观的用法是，不管原问题多么复杂，对偶问题都可能变得非常简单。
比如说，如果你对解决原问题毫无头绪，考虑它的对偶问题可能会有这些好处 :
-
如果原问题需要写simplex的init，对偶问题的基本解可能可行
-
如果原问题有大量的变量和很少的限制，对偶问题将具有很少的变量和大量的限制，反过来也是成立的
-
对偶问题可能是经典的(不过一般经典问题的对偶问题也是经典的)或者一眼的(比如它有简单的意义，或者它直接是个费用流之类的，这个我们刚才已经讨论过了)
，等等。接下来我们将通过几道例题带你领略一下。
NOI2008 志愿者招募
有\(m\)家公司的拖拉机可以租用，每家的拖拉机有一个费用\(c_i\)，租了之后可以在一个时间区间\(s_i,t_i\)使用(每一天都可以使用)，同一家公司的拖拉机价格相同，可以同时租用多台。接下来\(n\)天每天有一个拖拉机需求量\(a_i\)，问至少需要多少钱，才能满足每天都需求。\(n\leq 10^3,m\leq 10^4\)。
猜测这是网络流题，但是网络流不会建图，怎么办呢?可以simplex硬冲。因为既然可以用网络流来做，线性规划的最优解一定是整数解。
这题可以很容易地写出一个线性规划，它看起来像是这个样子 :
\[\min cx\\ \sum_{s_j\leq i\leq t_j}x_j\geq a_i(i=1,...,n)\]然后你发现这个不是很好冲，因为它的基本解不可行，我们需要写init。
考虑把它对偶一下，因为所有\(c\)都是正的，每一个约束都变成了\(\leq c_i\)，于是基本解可行了。直接转即可。
虽然\(n\)足有1e3，直接转居然就过了（
CF605C Freelancer’s Dreams
你在玩一个挂机游戏，有若干工作可以做，但是你同时只能做一项。你有两种资源，每一项每秒会给你提供\(a_i\)个第一种资源和\(b_i\)个第二种资源，你可以做任意实数秒并得到实数的资源。求最短的时间让你的两种资源分别超过\(x,y\)。\(n\leq 10^5\)。
容易写出线性规划。你发现它有\(n\)个变量和两个限制，这我们就不会了，于是对偶变成两个变量和\(n\)个限制。然后你发现这就是一个半平面交?做完了。
呃有两种做完的方法，一种是求出这个半平面交，另一种是直接根据半平面交的凸性三分。
CF1307G Cow and Exercise
给一个有向图，边权，每次给一个\(x\)，你可以把每一个边权加上一个实数，要求总共不能加超过\(t\)，最大化\(1\)到\(n\)的最短路。\(n\leq 50,q\leq 10^5\)。
呃看起来很困难。
这个题有很多推法，我们随便找一个。
注意到\(n\leq 50\)，可以想到费用流，于是我们开始想费用流，发现完全想不动怎么搞定这个最短路。
于是考虑钦定一个最短路，然后要求它就是最短路，也就是要满足三角形不等式。然后就可以写出一个线性规划，约束是所有的三角形不等式，边权只能增加，增加总量不超过\(t\)；目标是最大化\(dis(n)\)。
\[\max d_n\\ d_u-d_v+w_{u,v}+x_{u,v}\geq 0\\ \sum a_{u,v}\leq t\]其中\(w\)是邻接矩阵，\(x\)是增加的边权。
然后你发现这个不对，因为\(d_1\)可能不是\(0\)，但是加这么一个限制又不好看，所以我们把它改成
\[\max d_n-d_1\\ d_u-d_v+w_{u,v}+x_{u,v}\geq 0\\ \sum x_{u,v}\leq t\]这就对了。然后发现这是cf，所以肯定不能直接simplex，这个问题里面有个\(\sum x_{u,v}\leq t\)，它看起来不像可以转成费用流对偶的样子，因为它同时有两个方向的限制，没法把它去掉。
考虑换个方法，为了去除掉\(\sum x_{u,v}\leq t\)的限制，我们二分答案\(k\)，然后可以得到这样的线性规划
\[\min \sum x_{u,v}\\ d_u-d_v+w_{u,v}+x_{u,v}\geq 0\\ d_n-d_1\geq k\]这个看起来就好了一点。和费用流对偶中一样，这里的\(x\)也不重要了，因为我们是最小化\(x\)的和，每个\(x\)必然取下界\(\max(-w_{u,v}-d_u+d_v,0)\)。要保证\(d_n-d_1\geq k\)，我们可以先强行把它加进代价里试试，也就是说我们要求\(\min\left(\infty\cdot\max(k-d_n+d_1,0)+\sum\max(-w_{u,v}-d_u+d_v,0)\right)\)，其中\(\infty\)是一个极大值。这个还多了一项\(\infty\cdot\max(k-d_n+d_1,0)\)?
哦没关系的，因为\(w_{n,1}\)这条边不可能有用，所以我们可以用\(\max(-w_{n,1}-d_n+d_1,0)\)替换\(\infty\cdot\max(k-d_n+d_1,0)\)。于是现在完全变成了最大费用循环流的对偶形式。
所以我们建图就是，\(u\)到\(v\)连容量\(1\)，费用\(-w_{u,v}\)的边，特殊地，\(n\)到\(1\)连容量\(\infty\)，费用\(k\)的边。最大费用循环流即是要求的。
现在问题是\(n\rightarrow 1\)这条边的费用可能变化，并且这个费用是实数。考虑我们把这条边拿出来，剩下的问题就是\(1\)到\(n\)的最大费用流。注意到除了\(k\)以外所有数据都是整数，所以流量从整数开始增加不超过\(1\)的话，没有边会被充满，最短路就不会改变，于是在相邻整数之间最大费用流的费用是一次函数。
爆力跑出来每个流量的最大费用流，由于最大流量不可能超过\(n\)，这个复杂度是\(O(n^2m)\)。
二分答案\(k\)然后强行枚举最大费用流的流量\(f\)，然后已经算过了费用\(c_f\)，我们求一个\(\max\limits_f(fk+c_f)\)就是最大费用循环流，如果这个东西\(\leq x\)那就可行。由于拐点只可能是整点这样做是对的。复杂度是\(O(qn\log v)\)，不是很好跑。
然后可以把强行求值改成三分，因为费用流是凸的，它肯定也是单谷的。复杂度是\(O(q\log v\log n)\)。
更好的方法是观察\(\max\limits_f(fk+c_f)\leq x\)，它等价于对于任意\(f\)有\(k\leq\frac{x-c_f}{f}\)。于是我们知道答案就是\(\min\limits_f\frac{x-c_f}{f}\)，所以不需要二分答案，而只需要一次三分了。最后总共是\(O(n^2m+q\log n)\)。
洛谷8182 ezec-11 雪的魔法
考虑网络流，发现不是很会建啊?
佚名说的好，网络流输了的时候你就写个线性规划。考虑线性规划，这个我们会了，也就是给\([1,...,n-m+1]\)每个位置分配一个变量表示它开始的区间操作的次数，每个位置是一个约束，最小化所有变量的和。
对偶。此时每个位置是一个变量\(x_i\geq 0\)，约束是每个长\(m\)的区间和\(\leq 1\)，最大化\(\sum a_ix_i\)。
通过wiki可以知道，如果一个矩阵每一行的\(1\)是连续的，或者它可以通过若干置换变成这样，那么它是全幺模的。所以这个问题必然也存在一个全是整数的最优解，于是问题变成我们要选一些数，使得每个长\(m\)的区间最多有一个数被选，最大化选的数的和。于是我们会爆力dp了。
考虑如何处理区间查询。建立线段树，那么我们需要合并若干个区间，而一个区间由左右选的第一个元素的位置确定，于是一个区间的状态数是\(m^2\)，合并是简单的，于是查询单次\(O(m^3\log n)\)。当然考虑换成二区间合并结构，或者这里就是对序列分治，这样合并的时候只需要把左右卷起来，两边各少了\(m\)的状态数。处理一个长\(n\)的区间需要\(nm\)的代价，总共是\(O(nm\log n)\)，合并是\(O(m)\)，所以自然考虑根号分治。注意到如果我们有一个\(m>K\)的做法，那么递归到\(m>K\)的时候就改用这个做法，于是处理一个长\(n\)的区间的复杂度就变成\(nK\)，所以根号就把\(\log\)吃掉了(显然认为\(K=\Omega(n^{\epsilon})\))。
考虑\(m\)很大的时候，我们把序列每\(m\)个一块分成若干块，那么每一块选了最多一个。注意到如果一块选了第\(i\)个，那么如果前一块也选了，它只能选\(\leq i\)的，后一块只能选\(\geq i\)的。
考虑如果有一块没选，那么我们直接把左右加起来就行了，只需要枚举这一块，预处理一个分界线到任意一个位置的dp值。
考虑如果所有块都选了，那么刚才说的那个性质看起来像某种决策单调性，注意到把每一块看成一行，把块们竖着拼起来得到一个矩阵，那么问题相当于上面一行比下面一行选的更靠左，或者说我们画了一条折线。可以尝试画一画。
考虑继续分治，我们画一条竖线，也就是考虑每一块中间那个元素。考虑三种情况。
-
如果一个查询区间的第一段完全在(被查询区间经过的)第一块的右半边，或者最后一段完全在最后一块的左半边，那么答案必然都在右半边或左半边。我们把每一行的左半边拼成一个新的序列，右半边拼成一个新的序列，并相应修改\(m\)，把两种分别递归两边。递归若干次之后可能就\(m<K\)了，此时换用前面那个分治。
-
否则，如果一个查询的答案跨过了中线，那么有一个非常精巧的做法，我们把每一行的右半边和下一行的左半边作为一个新的块，则必然存在一块没有被选，所以可以用之前那个做法。
-
否则，也就是查询的答案没有跨过中线，注意到此时第一段在第一块的左半边的部分，或者最后一段在最后一块的右半边的部分必然没被选，所以上一个case的做法依然可行。
分治的部分是\(T(n)=2T(\frac{n}{2})+O(n\sqrt{n})=O(n\sqrt{n})\)。每个询问在每层会付出\(O(\sqrt{l})\)的代价，其中\(l\)是这一层的长度，所以总复杂度\(O((n+q)\sqrt{n})\)。我觉得这个题非常神。