题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1061
在WA了无数次之后终于A了（后来发现是数据范围开小了，ZKW费用流就是快，10个点只跑了0.12s），膜拜BYVoid大神的不等式建图法~~~
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 1010
struct node {
int t,f,c;
node *next,*pair;
node (){
next=pair=NULL;
}
};
node *head[MAXN];
void INSERT(int s,int t,int f,int c){
node *p=new(node);
p->t=t;
p->f=f;
p->c=c;
p->next=head[s];
head[s]=p;
p=new(node);
p->t=s;
p->f=0;
p->c=-c;
p->next=head[t];
head[t]=p;
head[s]->pair=head[t];
head[t]->pair=head[s];
}
int n,m;
int S,T;
int a[MAXN];
int dist[MAXN];
bool f[MAXN];
int cost=0;
int aug(int v,int flow){
if (v==T){
cost+=flow*dist[S];
return flow;
}
f[v]=false;
int rec=0;
for (node *p=head[v];p;p=p->next){
if (p->f&&f[p->t]&&dist[v]==dist[p->t]+p->c){
int ret=aug(p->t,min(flow-rec,p->f));
p->f-=ret;
p->pair->f+=ret;
if ((rec+=ret)==flow){
return flow;
}
}
}
return rec;
}
bool relabel(){
int delta=0x7fffffff;
for (int i=0;i++<T;){
if (!f[i]){
for (node *p=head[i];p;p=p->next){
if (p->f&&f[p->t]){
delta=min(delta,dist[p->t]+p->c-dist[i]);
}
}
}
}
if (delta==0x7fffffff){
return false;
}
for (int i=0;i++<T;){
if (!f[i]){
dist[i]+=delta;
}
}
return true;
}
int main(){
memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);
S=n+2;
T=S+1;
int x=0;
for (int i=0;i++<n;){
scanf("%d",&a[i]);
if (a[i]-x>=0){
INSERT(S,i,a[i]-x,0);
} else INSERT(i,T,x-a[i],0);
x=a[i];
}
INSERT(n+1,T,a[n],0);
for (int i=0;i++<m;){
int s,t,c;
scanf("%d%d%d",&s,&t,&c);
INSERT(s,t+1,0x7fffffff,c);
}
for (int i=1;i++<n+1;){
INSERT(i,i-1,0x7fffffff,0);
}
memset(dist,0,sizeof(dist));
do {
do {
memset(f,true,sizeof(f));
} while (aug(S,0x7fffffff));
} while (relabel());
printf("%d\n",cost);
return 0;
}
