题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3265
（这道题基本跟NOI08的employee思路一致，构图神马的就不多说了（详见BYVoid大神的Blog））
代码（自己写的裸ZKW费用流，实在很慢，不过也是过了~）：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 10010
#define MAXM 100010
struct node {
int t,f,c;
node *next,*pair;
} *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[MAXM],t[MAXM],c;
int a[MAXN];
int S,T;
int dist[MAXN];
bool f[MAXN];
int cost=0;
int aug(int v,int flow){
if (v==T){
cost+=dist[S]*flow;
return flow;
}
f[v]=false;
int rec=0;
for (node *p=head[v];p;p=p->next){
if (f[p->t]&&dist[v]==dist[p->t]+p->c&&p->f){
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 (f[p->t]&&p->f){
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));
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
S=n+2;
T=S+1;
for (int i=0;i++<n;){
scanf("%d",&a[i]);
}
for (int i=0;i++<n+1;){
if (a[i]-a[i-1]>=0){
INSERT(S,i,a[i]-a[i-1],0);
} else INSERT(i,T,a[i-1]-a[i],0);
if (i>1){
INSERT(i,i-1,0x7fffffff,0);
}
}
for (int i=0;i++<m;){
int k;
scanf("%d",&k);
for (int j=0;j<k;j++){
scanf("%d%d",&s[j],&t[j]);
}
scanf("%d",&c);
for (int j=0;j<k;j++){
INSERT(s[j],t[j]+1,0x7fffffff,c);
}
}
memset(dist,0,sizeof(dist));
do {
do {
memset(f,true,sizeof(f));
} while (aug(S,0x7fffffff));
} while (relabel());
printf("%d\n",cost);
return 0;
}
