最小费用流与线性规划
最小费用流问题可以考虑看成一个线性规划问题。
设 $f_{u，v}$ 为边的流量，$c_{u,v}$ 表示边的容量，$w_{u,v}$ 表示边的代价。$V$ 表示点集，$E$ 表示边集，记总的流量为 $F$。
那么最小费用流问题等价于：
- 求 $\min{ \sum f_{u,v}w_{u,v} }$
- 限制：
- 对所有 $u\in V$，有：
$$
\sum\limits_{(v,u)\in E}f_{v,u}-\sum\limits_{(u,v)\in E}f_{u,v}=\begin{cases}
F,if\ u=n\
-F,if\ u=1\
0,otherwise
\end{cases}
$$
- 对所有 $u\in V$，有：
- 对所有 $(u,v)\in E$，有 $0\le f_{u,v}\le c_{u,v}$。
- 共 $m$ 个变量 $f_{u,v}$，$n+m$ 条限制。
给出线性规划一般形式和其对偶问题：
原问题：
$$
\begin{aligned}
\max z&=\sum\limits_{j=1}^m c_jx_j\
Ax&\le b\
x&\ge 0
\end{aligned}
$$
对偶问题：
$$
\begin{aligned}
\min w&=\sum\limits_{j=1}^nb_jy_j\
A^Ty&\ge c\
y&\ge 0
\end{aligned}
$$
这里 $A,x,b,c,y$ 均为矩阵，其中 $A$ 为 $n\times m$ 矩阵，$x,c$ 为 $n\times 1$ 矩阵，$y,b$ 为 $m\times 1$ 矩阵。定义矩阵之间的 $\le$ 为对应位置都需要小于。
不加证明的给出以下定理：
- 线性规划和其对偶线性规划等价。
这里不给证明的原因是该定理证明较为繁杂，博主不会证明，且本博客内容与该性质内容关系不大。
把最小费用流问题对应线性规划的限制转化成一般形式：
$$
\begin{cases}
+\sum f_{v,u}-\sum f_{u,v}&\ge a_i\
-\sum f_{u,v} + \sum f_{u,v}&\ge a_i\
-f_{u,v}\ge -c_{u,v}
\end{cases}
$$
其中 $a_u$ 表示点 $u$ 应该的流量: $F,-F$ 或 $0$。
把这个线性规划的对偶形式写出来，限制一共有 $2n+m$ 个，考虑前 $n$ 个限制代表变量为 $q_i$，另外 $n$ 个限制代表变量为 $e_i$，后 $m$ 个限制设为 $r_{u,v}$。
考虑前 $2n$ 个向量与限制的对应关系，对于一个限制来说，显然我们可以让 $q_u$ 来对应 $+\sum f_{v,u}-\sum f_{u,v}\ge a_i$，这样所有 $f_{v,u}$ 代表的位置会有 $+q_u$，$f_{v,u}$ 代表的位置会有 $-q_u$。强烈建议各位读者画一个矩阵自己感受一下。
最后化成对偶线性规划为：
- 求 $\max{ \sum a_u q_u-\sum\ a_ue_u-\sum r_{u,v}{w_{u,v}} }$
- 限制：
- 对于所有 $(u,v)\in E$，有：$-q_u+q_v+e_u-e_v-r_{u,v}\le w_{u,v}$
- $q_u,e_u,r_{u,v}\ge 0$
- 一共 $m$ 条限制。
需要注意在推式子的时候，特别关注一下无入度点和无出度点的的情况，它们也是满足条件的。
发现所有式子都与 $q_u-e_u$ 有关，不如设其为 $d_u$。以及注意到 $a_u$ 除了 $1,n$ 都是 $0$，所以线性规划变成：
- 求 $\max{ F(d_n-d_1)-\sum r_{u,v}{c_{u,v}} }$
- 限制：
- 对于所有 $(u,v)\in E$，有：$d_v\le d_u+r_{u,v}+w_{u,v}$
- $d_u,r_{u,v}\ge 0$
- 一共 $m$ 条限制。
$d_u$ 依然满足 $\ge0$ 的原因是，考虑如果找到了一组满足条件的 $d$，那么把 $d$ 同加到 $\ge 0$ 依然满足条件。
Solution
题目大意：给定 $n$ 个点 $m$ 条边的有向图，边权为 $w$，可以选择把一条边的边权 $w_i$ 修改为 $w_i+a_i$，$a_i$ 可以为实数，但是需要满足 $a_i\ge 0,\sum a_i\le x$，有 $q$ 次询问，每次给定 $x$，询问修改之后 $1$ 到 $n$ 最短路的最大值，每次询问独立，无重边无自环。$n\le 50,w_i\le 10^6,w\le 10^5$
关注我们的对偶问题，发现限制如同最短路，而 $r_{u,v}$ 就像我们给每条边加上的权值 $a_i$。
关注我们对偶线性规划求的东西，可以令 $c_{u,v}=1$，那么现在变成了求 $\max{ F(d_n-d_1)-\sum r_{u,v} }$，其中后者相当于我们更改的权值总和，设为 $C$，同时记 $D=d_n-d_1$ 设为最短路。
我们把所有有用的 $(C,D)$ 映射到二维平面上，形成的图形一定是上凸壳，且斜率最大是 $1$。并且，凸壳上的拐点一定都是整点。且如果让 $a_i$ 都是整数，那么显然随着 $C$ 的增加，$D$ 要么不变，要么加一，在这个情况下建立凸包，而考虑如果令 $a_i$ 可以为实数，不难发现凸包不会变化。如图：
如果令所有 $a_i$ 都是整数，那么点应该是 $E,F,G$，而如果 $a_i$ 可以为实数，那么点 $I,J,K$。
由此可以得出结论，凸包上的所有切线都形如 $\frac{1}{x}$ 的形式，其中 $x$ 是整数。
设 $A(F)=\max_{D,C}{ FD-C }$，设对于给定 $F$，有 $A(F)=FD_F-C_F$，那么 $D_F=\frac{A(F)}{F}+\frac{C_F}{F}$。由此可知，若给定 $F$ 求 $A(F)$，方法即为用 $\frac{1}{F}$ 去切这个凸包，而切线与 $x$ 轴的截距为 $A(F)$。
原问题等价于给定 $C$，要求在凸包上找到 $x=C$ 与凸壳的交点 $(C,D)$。考虑所有的 $F$ 和它们对应的切线在 $x=C$ 处的值，设为 $y$，不难发现有 $y\ge D$，且一定存在一个 $x$，使得 $y=D$，即一条与凸包相切且切点为 $(C,D)$ 的切线。则答案为 $\min_F{ \frac{A(F)}{F}+\frac{C}{F} }$。
现在唯一的问题是 $F$ 是可以为实数的，一个方法是可以二分，不过不用这么麻烦。我们其实只用考虑 $F$ 是整数的情况，这是因为凸包上所有的斜率都形如 $\frac{1}{x}$，所有对于凸包上每个点 $(C,D)$，都存在一个整数 $F$ 使得斜率为 $\frac{1}{F}$ 的切线经过这个点。
所以，我们枚举 $F$，通过费用流算出 $A(F)$，对于每个询问，算出 $\min_F{ \frac{A(F)}{F}+\frac{C}{F} }$ 即可。
代码
1 | int n,m; |