lz问：费用流怎么写
波老师答：我前几天才做一道费用流……
结果……诶这题以前好像做过，但是搞啥啊？！（scy：这锅我不背）
mod题解：https://www.byvoid.com/zhs/blog/noi-2008-employee
#include<cstdio> #include<iostream> #include<cstring> using namespace std; struct node { int x,y,c,d,next,other; }a[510000];int len,last[111000]; void ins(int x,int y,int c,int dd) { int k1,k2; len++;k1=len; a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=dd; a[len].next=last[x];last[x]=len; len++;k2=len; a[len].x=y;a[len].y=x;a[len].c=0;a[len].d=-dd; a[len].next=last[y];last[y]=len; a[k1].other=k2; a[k2].other=k1; } int n,m,st,ed,ans; int d[110000],list[110000]; bool v[110000]; int pre[110000],cc[110000]; bool spfa() { memset(cc,0,sizeof(cc));cc[st]=2147483647; memset(v,false,sizeof(v));v[st]=true; memset(d,63,sizeof(d));d[st]=0; int head=1,tail=2;list[1]=st; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[y]>d[x]+a[k].d&&a[k].c>0) { d[y]=(d[x]+a[k].d); if(v[y]==false) { v[y]=true; list[tail++]=y; if(tail==ed+1)tail=1; } cc[y]=min(cc[x],a[k].c); pre[y]=k; } } v[x]=false; head++;if(head==ed+1)head=1; } if(d[ed]>=999999999)return false; int x=ed; while(x!=st) { int k=pre[x]; a[k].c-=cc[ed];a[a[k].other].c+=cc[ed]; ans+=a[k].d*cc[ed]; x=a[k].x; } return true; } int p[110000]; int main() { int x,y,c,dd; scanf("%d%d",&n,&m);st=n+2;ed=n+3; for(int i=1;i<=n;i++)scanf("%d",&p[i]); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&dd); ins(y+1,x,99999999,dd); } p[0]=0;p[n+1]=0; for(int i=1;i<=n+1;i++) { c=p[i]-p[i-1]; if(c>=0)ins(i,ed,c,0); else ins(st,i,-c,0); if(i!=n+1)ins(i,i+1,99999999,0); } ans=0; while(spfa()==true); printf("%d ",ans); return 0; }