这一题有点麻烦
后来参看了BYVoid大神犇的题解才有点明白
一直以为这是DP233333
好了，下面就是我的题解：
例如，有这样的一组数据
5 6
5 7 4 3 2
1 4 3
3 5 2
2 4 5
1 3 2
1 1 1
2 3 3
那么，我们有：
\[\begin{cases}x_1+x_4+x_5\ge5\\x_1+x_3+x_4+x_6\ge 7\\x_1+x_2+x_3+x_4+x_6\ge 4\\x_1+x_2+x_3\ge 3\\x_2\ge 2\end{cases}\]我居然突然明白了为何是网络流了，这题居然是线性规划！！！
好了，我们现在就要求\(ans=x_1c_1+x_2c_2+x_3c_3+x_4c_4+x_5c_5+x_6c_6\)的最小值！
这里是个6元的不等式，要用六维的生物做，题目里有10000维，那么要10000维生物做，那里的图差不多就是这样（笑~）
好了，我们可以这样：
\[\begin{cases}x_1+x_4+x_5+y_1=5\\x_1+x_3+x_4+x_6+y_2=7\\x_1+x_2+x_3+x_4+x_6+y_3=4\\x_1+x_2+x_3+y_4=3\\x_2+y_5=2\end{cases}\]再加上一个式子
\[\begin{cases}x_1+x_4+x_5+y_1=5\\x_1+x_3+x_4+x_6+y_2=7\\x_1+x_2+x_3+x_4+x_6+y_3=4\\x_1+x_2+x_3+y_4=3\\x_2+y_5=2\\0=0\end{cases}\]用第\(i\)个式子减去第\(i-1\)个式子，有：
\[\begin{cases}x_1+x_4+x_5+y_1=5\\x_3-x_5+x_6-y_1+y_2=2\\x_2-x_6-y_2+y_3=-3\\-x_4-y_3+y_4=-1\\-x_1-x_3-y_4+y_5=-1\\-x_2-y_5=-2\end{cases}\]接下来是构图，有以下约定：
设一个通式，即第\(i\)个式子表示为：\(\sum x_j+\sum y_j=c_i\)
若\(c_i\ge 0\)则连边：\(S\rightarrow i\)，反之连边：\(i\rightarrow T\)，边权为0，容量为\(abs(c_i)\)
若\(i\)式中，\(x_j\)的系数为正，\(k\)式中，\(x_j\)的系数为负，则连边\(i\rightarrow j\)边权为\(C_j\)，容量为INF
若\(i\)式中，\(y_j\)的系数为正，\(k\)式中，\(y_j\)的系数为负，则连边\(k\rightarrow i\)边权为0，容量为INF
然后，求\(S\rightarrow T\)的最小费用最大流即可
下面是AC-Code：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN=1005,MAXM=40005;
const long long INF=0x7fffffff;
//网络流用
struct Edge{int next,op,t,v,w;}E[MAXM];
int Pfirst[MAXN];
int DIS[MAXN];
int Pre[MAXN];
int Edg[MAXN];
int NEED[MAXN];
bool INQ[MAXN];
int M,N;
int COST;
int S=0,T;
int totE=0;
void addedge(int s,int t,int w,int v)//源汇权容
{
int E1=++totE,E2=++totE;
E[E1].t=t;E[E2].t=s;
E[E1].next=Pfirst[s];E[E2].next=Pfirst[t];
E[E1].op=E2;E[E2].op=E1;
E[E1].w=w;E[E2].w=-w;
E[E1].v=v;E[E2].v=0;
Pfirst[s]=E1;Pfirst[t]=E2;
}
void Read()
{
int SS,TT,CC,c;
scanf("%d%d",&N,&M);
T=N+2;
for (int i=1;i<=N;i++)
scanf("%d",&NEED[i]);
for (int i=1;i<=N+1;i++)
{
if (i!=1)
addedge(i,i-1,0,INF);
c=NEED[i]-NEED[i-1];
if (c>=0)
addedge(0,i,0,c);
else
addedge(i,T,0,-c);
}
for (int i=1;i<=M;i++)
{
scanf("%d%d%d",&SS,&TT,&CC);
addedge(SS,TT+1,CC,INF);
}
}
void SPFA()
{
int u,v;
memset(DIS,0x3f,sizeof(DIS));
memset(Pre,-1,sizeof(Pre));
memset(INQ,0,sizeof(INQ));
DIS[S]=0;
queue <int>Q;
Q.push(S);
while (!Q.empty())
{
u=Q.front();
Q.pop();
INQ[u]=false;
for (int pv=Pfirst[u];pv;pv=E[pv].next)
{
v=E[pv].t;
if (E[pv].v>0)
{
if (DIS[v]>(DIS[u]+E[pv].w))
{
if (!INQ[v])
{
Q.push(v);
INQ[v]=true;
}
Edg[v]=pv;
Pre[v]=u;
DIS[v]=DIS[u]+E[pv].w;
}
}
}
}
}
void MaxFlow()
{
int u,v;
int tmaxflow;
while (1)
{
SPFA();
if (Pre[T]==-1)
break;
tmaxflow=INF;
for (v=T;Pre[v]!=-1;v=Pre[v])
{
tmaxflow=min(tmaxflow,E[Edg[v]].v);
}
for (v=T;Pre[v]!=-1;v=Pre[v])
{
COST+=tmaxflow*E[Edg[v]].w;
E[Edg[v]].v-=tmaxflow;
E[E[Edg[v]].op].v+=tmaxflow;
}
}
printf("%d\n",COST);
}
int main()
{
Read();
MaxFlow();
return 0;
}