以前写的1061但一直没懂，后来懂了但忘写解题报告了

做了1283顺便补一下吧

1061 我是orz https://www.byvoid.com/blog/noi-2008-employee/#more-916

这类类似线性规划的费用流构造，大概有这么几个步骤

首先找出不等式约束关系，然后添加辅助变量变成等式，并写出目标函数

然后通过做差构造，使每个变量都出现在两个等式中

每个等式整理成变量+常量=0 根据入流=出硫，我们把每个等式作为一个点

如果我们把等式左边系数为正作为入流，系数为负作为出流

则，对于每个变量，如果在等式j出现时系数为正，等式k系数为-，则k向j连边 流量为无穷，费用由目标函数决定

如果是常量，正则源点向这个等式连边，负则其向汇点连边，流量为常量的绝对值

然后我们就可以跑费用流了

1 const inf=2147483647;  2   3 type node=record  4        next,point,flow:longint;  5        cost:int64;  6      end;  7   8 var edge:array[0..1000010] of node;  9     c,p,cur,pre:array[0..1010] of longint; 10     d:array[0..1010] of int64; 11     v:array[0..1010] of boolean; 12     q:array[0..1000010] of longint; 13     b,e,w,i,j,n,m,len,t:longint; 14     ans:int64; 15  16 procedure add(x,y,f:longint;w:int64); 17   begin 18     inc(len); 19     edge[len].point:=y; 20     edge[len].flow:=f; 21     edge[len].cost:=w; 22     edge[len].next:=p[x]; 23     p[x]:=len; 24   end; 25  26 function spfa:boolean; 27   var  f,r,x,y,i:longint; 28   begin 29     f:=1; 30     r:=1; 31     q[1]:=0; 32     for i:=1 to t do 33       d[i]:=inf; 34     fillchar(v,sizeof(v),false); 35     v[0]:=true; 36     while f<=r do 37     begin 38       x:=q[f]; 39       v[x]:=false; 40       i:=p[x]; 41       while i<>-1 do 42       begin 43         y:=edge[i].point; 44         if edge[i].flow>0 then 45           if d[y]>d[x]+edge[i].cost then 46           begin 47             d[y]:=d[x]+edge[i].cost; 48             pre[y]:=x; 49             cur[y]:=i; 50             if not v[y] then 51             begin 52               inc(r); 53               q[r]:=y; 54               v[y]:=true; 55             end; 56           end; 57         i:=edge[i].next; 58       end; 59       inc(f); 60     end; 61     if d[t]=inf then exit(false) else exit(true); 62   end; 63  64 procedure mincost; 65   var i,j:longint; 66       neck:int64; 67   begin 68     while spfa do 69     begin 70       neck:=inf; 71       i:=t; 72       while i<>0 do 73       begin 74         j:=cur[i]; 75         if edge[j].flow
      
       0 do 80       begin 81         j:=cur[i]; 82         dec(edge[j].flow,neck); 83         inc(edge[j xor 1].flow,neck); 84         i:=pre[i]; 85       end; 86       ans:=ans+d[t]*neck; 87     end; 88   end; 89  90 begin 91   readln(n,m); 92   len:=-1; 93   fillchar(p,sizeof(p),255); 94   t:=n+2; 95   for i:=1 to n do 96     read(c[i]); 97   for i:=1 to m do 98   begin 99     readln(b,e,w);100     add(b,e+1,inf,w);101     add(e+1,b,0,-w);102   end;103   for i:=1 to n+1 do104   begin105     w:=c[i]-c[i-1];106     if w>=0 then107     begin108       add(0,i,w,0);109       add(i,0,-w,0);110     end111     else begin112       add(i,t,-w,0);113       add(t,i,0,0);114     end;115     if i>1 then116     begin117       add(i,i-1,inf,0);118       add(i-1,i,0,0);119     end;120   end;121   mincost;122   writeln(ans);123 end.
      

1 type node=record 2        po,next,flow,cost:longint; 3      end; 4  5 var e:array[0..800010] of node; 6     d,pre,cur,p:array[0..1010] of longint; 7     v:array[0..1010] of boolean; 8     q:array[0..1000010] of longint; 9     i,x,y,n,m,len,t,k:longint;10 11 procedure add(x,y,f,c:longint);12   begin13     inc(len);14     e[len].po:=y;15     e[len].flow:=f;16     e[len].cost:=c;17     e[len].next:=p[x];18     p[x]:=len;19   end;20 21 procedure build(x,y,f,c:longint);22   begin23     add(x,y,f,c);24     add(y,x,0,-c);25   end;26 27 function spfa:boolean;28   var i,f,r,x,y:longint;29   begin30     fillchar(v,sizeof(v),false);31     for i:=1 to t do32       d[i]:=-1000000007;33     d[0]:=0;34     f:=1;35     r:=1;36     q[1]:=0;37     while f<=r do38     begin39       x:=q[f];40       v[x]:=false;41       i:=p[x];42       while i<>-1 do43       begin44         y:=e[i].po;45         if e[i].flow>0 then46           if d[y]
      
       0 do73       begin74         j:=cur[i];75         dec(e[j].flow);76         inc(e[j xor 1].flow);77         i:=pre[i];78       end;79       maxcost:=maxcost+d[t];80     end;81   end;82 83 begin84   readln(n,m,k);85   len:=-1;86   fillchar(p,sizeof(p),255);87   t:=n+1;88   for i:=1 to n do89   begin90     read(x);91     y:=i+m;92     if y>n then y:=t;93     build(i,y,1,x);94     build(i,i+1,k,0);95   end;96   build(0,1,k,0);97   writeln(maxcost);98 end.
      

 UPD：这种题目可以直接跑单纯形

但是为什么单纯形能保证用最优解一定是整数呢，求神犇教导