====== 线性规划 ======
===== 标准型 =====
描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分:
* 一个需要极大 / 极小化的线性函数:
$$\sum_{i=1}^{n}x_ik_i$$
* 以下形式的问题约束:
$$\left\{\begin{aligned}
a_{11}x_1+a_{12}x_2+&\cdots +a_{1n}x_n\le b_1\\
a_{21}x_1+a_{22}x_2+&\cdots +a_{2n}x_n\le b_2\\
\ &\cdots\\
a_{m1}x_1+a_{m2}x_2+&\cdots +a_{mn}x_n\le b_m\\
\end{aligned}\right.
$$
* 和非负变量:
$$x_i\ge 0$$
===== 费用流求解特殊的线性规划问题 =====
先引入一些值恒正的松弛变量,将不等式组转化为等式组。
将每个等式看做一个点,当**在特殊情况下**如果能构造出“对于所有变量,在等式组中分别在左端和右端出现恰好一次,系数均为 $1$ ”的等式组,那么很容易对于每个变量 $x$ 在点(等式)之间进行连边:
例如,等式 $p$ 中,$x$ 出现在等式左端且系数为 $1$ ,等式 $q$ 中,$x$ 出现在等式右端且系数为 $1$ ,那么连边 $p\rightarrow q$ ,流量和费用具体题目进行分析。
另外按需连接源、汇、等式之间通过常数项的连边。最终让连边满足**除了源汇,每个点的出流量等于入流量**,这样就可以用**费用流**求出最小或最大费用,而同时这个边的流量便是这个变量的取值。
在特殊的题目中,我们可以加入两个 $0=0$ 的方程并在等式组之间差分,达到这样的要求。
==== 模板题 ====
[[https://codeforces.com/gym/101190|NEERC 2016 D. Delight for a Cat]]
**题意**:有一个人,在某一时刻可以睡觉也可以吃饭,要求连续 $k$ 时刻至少有 $m_s$ 时间在睡觉,至少有 $m_e$ 时刻在吃饭。给定特定时刻睡觉 / 吃饭的快乐值,求最大快乐值以及方案。
**题解**:先默认他一直吃饭,设 $x_i$ 表示第 $i$ 时刻他是不是在睡觉,很明显 $x_i\in\{0,1\}$ ,故关于 $x_i$ 的连边,长度为 $1$ ,费用为 $-(s_i-e_i)$ (取负是为了求最小费用)。然后列出不等式组,加入松弛变量转化成等式组:
$$\left.\begin{aligned}
0&=0\\
y_1+x_1+x_2+\cdots +x_k&=k-m_e\\
x_1+x_2+\cdots +x_k &=m_s+z_1\\
y_2+x_2+x_3+\cdots +x_{k+1}&=k-m_e\\
x_2+x_3+\cdots +x_{k+1} &=m_s+z_2\\
\ \cdots\\
y_{n-k+1}+x_{n-k+1}+x_{n-k+2}+\cdots +x_n&=k-m_e\\
x_{n-k+1}+x_{n-k+2}+\cdots +x_n &=m_s+z_{n-k+1}\\
0&=0
\end{aligned}\right.
$$
差分:
$$\left.\begin{aligned}
y_1+x_1+x_2+\cdots +x_k&=k-m_e\\
k-m_e-m_s &=y_1+z_1\\
x_{k+1}+z_1+y_2&=x_1+k-m_e-m_s\\
k-m_e-m_s &=y_2+z_2\\
\ \cdots\\
x_{n}+z_1+y_2&=x_{n-k}+k-m_e-m_s\\
k-m_e-m_s &=y_{n-k+1}+z_{n-k+1}\\
m_s+z_{n-k+1}&=x_{n-k+1}+x_{n-k+2}+\cdots +x_n\\
\end{aligned}\right.
$$
连边跑一遍最小费用最大流即可。
#include
#include
#include
#include
==== 练习题 ====
[[https://www.luogu.com.cn/problem/P3980|NOI 2008 志愿者招募]] [[https://byvoid.com/zhs/blog/noi-2008-employee/|题解]]
**题意**:有 $n$ 天, $m$ 种工作时间为 $[s_i,t_i]$ ,工资为 $v_i$ 的志愿者,每个时间点有志愿者个数要求,求最小花费。
**题解**:抽象出来每个方程的样子,发现对于每个 $x_i$ ,差分之后连的是一条 $s_i\rightarrow t_i+1$ 的边,松弛变量和常数与上题类似。
#include
#include
#include
#include