线性规划定义：
在给定有限的资源和竞争约束情况下，很多问题都可以表述为最大化或最小化某个目标。如果可以把目标指定为某些变量的线性函数，而且如果可以将资源约束指定为这些变量的等式或不等式，则得到了一个线性规划问题。
对于一些线性规划问题，我们通常能够转化成 每个变量的都出现两次，且系数分别为+1和-1。
就是这样的模型，我们可以用网络流的方法巧妙的解决。
首先网络流有性质：对于除了源点和汇点的其他点，有 流入的总量等于流出的总量。
这让我们有一个思路，把点当成每一个方程，把边看成给予限制的变量，对于每个变量，把+1看成流出-1看成流入，找到对应方程的位置连边。
如果给出的是线性不等式，就加上一个变量将其转化为线性等式。
看一道例题：BZOJ1061: [Noi2008]志愿者招募
Description
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难
题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要
Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用
是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这
并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
设第i类志愿者招募xi个。
于是可以列出方程：
$\begin{matrix}
xi\ge 0\\
x1\ge 2\\
x1+x2\ge 3\\
x2+x3\ge 4\\
\end{matrix}$
xi\ge 0\\
x1\ge 2\\
x1+x2\ge 3\\
x2+x3\ge 4\\
\end{matrix}$
但是这个东西是不等式，于是加入一个变量y使得方程变为线性等式。
$\begin{matrix}
xi\ge 0\\
yi\ge 0\\
x1= y1\\
x1+x2= y2+3\\
x2+x3= y3+4\\
\end{matrix}$
xi\ge 0\\
yi\ge 0\\
x1= y1\\
x1+x2= y2+3\\
x2+x3= y3+4\\
\end{matrix}$
此时变量出现次数不对，考虑每个变量出现都是一段连续的区间，那么我们差分一下，就变成每个变量只出现两次并且一次系数为+1一次系数为-1。
注意最后一行也要差分，就是说现在多了一个方程，这样：
$\begin{matrix}
xi\ge 0\\
yi\ge 0\\
x1-y1= 0\\
x2-y2+y1-3= 0\\
x3-x1-y3+y2= 0\\
-x2-x3-y4+y3=0
\end{matrix}$
$\begin{matrix}
xi\ge 0\\
yi\ge 0\\
x1-y1= 0\\
x2-y2+y1-3= 0\\
x3-x1-y3+y2= 0\\
-x2-x3-y4+y3=0
\end{matrix}$
于是建图就比较清晰了。
n+1个方程当做点。对于变量xi，从系数为+1的方程向系数为-1的方程连(inf,a[i])的边。
其中括号前面表示容量，后面表示费用,即S[i]->T[i]+1(inf,a[i])
对于变量yi，和xi差不多，也是从系数为+1的方程向系数为-1的方程连(inf,0)的边,
即i+1->i(inf,0)
对于常数项，若该常数项系数为正，则从S向其连边，容量为c[i]-c[i-1]，否则从i向T连边，容量为c[i-1]-c[i]。
然后跑最小费用最大流即可。
总结一下建图吧，当我们把方程化成适合网络流求解的形式后，只需要把系数为+1的方程向系数为-1的方程连边即可。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10050
#define M 100050
#define S (10049)
#define T (10048)
#define inf (1<<30)
int head[N],to[M],nxt[M],flow[M],val[M],cnt=1,path[N],Q[N],l,r,dis[N],inq[N],n,m,a[N],c[M],s[N],t[N];
inline void add(int u,int v,int f,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f; val[cnt]=w;
to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0; val[cnt]=-w;
}
bool spfa() {
memset(dis,0x3f,sizeof(dis));
memset(path,0,sizeof(path));
l=r=0; Q[r++]=S; dis[S]=0; inq[S]=1;
while(l!=r) {
int x=Q[l++],i; if(l==n+10) l=0; inq[x]=0;
for(i=head[x];i;i=nxt[i]) {
if(flow[i]&&dis[to[i]]>dis[x]+val[i]) {
dis[to[i]]=dis[x]+val[i];
path[to[i]]=i^1;
if(!inq[to[i]]) {
Q[r++]=to[i]; if(r==n+10) r=0; inq[to[i]]=1;
}
}
}
}
return path[T];
}
void mcmf() {
int minc=0,maxf=0;
while(spfa()) {
int nf=1<<30,i;
for(i=T;i!=S;i=to[path[i]]) {
nf=min(nf,flow[path[i]^1]);
}
for(i=T;i!=S;i=to[path[i]]) {
flow[path[i]]+=nf;
flow[path[i]^1]-=nf;
minc+=nf*val[path[i]^1];
}
maxf+=nf;
}
printf("%d\n",minc);
}
int main() {
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++) {
scanf("%d",&c[i]); add(i+1,i,inf,0);
}
for(i=1;i<=m;i++) {
scanf("%d%d%d",&s[i],&t[i],&a[i]);
add(s[i],t[i]+1,inf,a[i]);
}
for(i=1;i<=n+1;i++) {
if(c[i]-c[i-1]>0) {
add(S,i,c[i]-c[i-1],0);
}else {
add(i,T,c[i-1]-c[i],0);
}
}
mcmf();
}