描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：

• 一个需要极大 / 极小化的线性函数：

$$\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$ 的方程并在等式组之间差分，达到这样的要求。

模板题：NOI 2008 志愿者招募 题解

练习题：NEERC 2016 D. Delight for a Cat