以前写的1061但一直没懂，后来懂了但忘写解题报告了
做了1283顺便补一下吧
1061 我是orz https://www.byvoid.com/blog/noi-2008-employee/#more-916
这类类似线性规划的费用流构造，大概有这么几个步骤
首先找出不等式约束关系，然后添加辅助变量变成等式，并写出目标函数
然后通过做差构造，使每个变量都出现在两个等式中
每个等式整理成变量+常量=0 根据入流=出硫，我们把每个等式作为一个点
如果我们把等式左边系数为正作为入流，系数为负作为出流
则，对于每个变量，如果在等式j出现时系数为正，等式k系数为-，则k向j连边 流量为无穷，费用由目标函数决定
如果是常量，正则源点向这个等式连边，负则其向汇点连边，流量为常量的绝对值
然后我们就可以跑费用流了
const inf=; type node=record
next,point,flow:longint;
cost:int64;
end; var edge:array[..] of node;
c,p,cur,pre:array[..] of longint;
d:array[..] of int64;
v:array[..] of boolean;
q:array[..] of longint;
b,e,w,i,j,n,m,len,t:longint;
ans:int64; procedure add(x,y,f:longint;w:int64);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=w;
edge[len].next:=p[x];
p[x]:=len;
end; function spfa:boolean;
var f,r,x,y,i:longint;
begin
f:=;
r:=;
q[]:=;
for i:= to t do
d[i]:=inf;
fillchar(v,sizeof(v),false);
v[]:=true;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
if d[y]>d[x]+edge[i].cost then
begin
d[y]:=d[x]+edge[i].cost;
pre[y]:=x;
cur[y]:=i;
if not v[y] then
begin
inc(r);
q[r]:=y;
v[y]:=true;
end;
end;
i:=edge[i].next;
end;
inc(f);
end;
if d[t]=inf then exit(false) else exit(true);
end; procedure mincost;
var i,j:longint;
neck:int64;
begin
while spfa do
begin
neck:=inf;
i:=t;
while i<> do
begin
j:=cur[i];
if edge[j].flow<neck then neck:=edge[j].flow;
i:=pre[i];
end;
i:=t;
while i<> do
begin
j:=cur[i];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
i:=pre[i];
end;
ans:=ans+d[t]*neck;
end;
end; begin
readln(n,m);
len:=-;
fillchar(p,sizeof(p),);
t:=n+;
for i:= to n do
read(c[i]);
for i:= to m do
begin
readln(b,e,w);
add(b,e+,inf,w);
add(e+,b,,-w);
end;
for i:= to n+ do
begin
w:=c[i]-c[i-];
if w>= then
begin
add(,i,w,);
add(i,,-w,);
end
else begin
add(i,t,-w,);
add(t,i,,);
end;
if i> then
begin
add(i,i-,inf,);
add(i-,i,,);
end;
end;
mincost;
writeln(ans);
end.
1061
type node=record
po,next,flow,cost:longint;
end; var e:array[..] of node;
d,pre,cur,p:array[..] of longint;
v:array[..] of boolean;
q:array[..] of longint;
i,x,y,n,m,len,t,k:longint; procedure add(x,y,f,c:longint);
begin
inc(len);
e[len].po:=y;
e[len].flow:=f;
e[len].cost:=c;
e[len].next:=p[x];
p[x]:=len;
end; procedure build(x,y,f,c:longint);
begin
add(x,y,f,c);
add(y,x,,-c);
end; function spfa:boolean;
var i,f,r,x,y:longint;
begin
fillchar(v,sizeof(v),false);
for i:= to t do
d[i]:=-;
d[]:=;
f:=;
r:=;
q[]:=;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=e[i].po;
if e[i].flow> then
if d[y]<d[x]+e[i].cost then
begin
d[y]:=d[x]+e[i].cost;
pre[y]:=x;
cur[y]:=i;
if not v[y] then
begin
inc(r);
q[r]:=y;
v[y]:=true;
end;
end;
i:=e[i].next;
end;
inc(f);
end;
if d[t]<= then exit(false) else exit(true);
end; function maxcost:longint;
var i,j:longint;
begin
maxcost:=;
while spfa do
begin
i:=t;
while i<> do
begin
j:=cur[i];
dec(e[j].flow);
inc(e[j xor ].flow);
i:=pre[i];
end;
maxcost:=maxcost+d[t];
end;
end; begin
readln(n,m,k);
len:=-;
fillchar(p,sizeof(p),);
t:=n+;
for i:= to n do
begin
read(x);
y:=i+m;
if y>n then y:=t;
build(i,y,,x);
build(i,i+,k,);
end;
build(,,k,);
writeln(maxcost);
end.
1283
UPD：这种题目可以直接跑单纯形
但是为什么单纯形能保证用最优解一定是整数呢，求神犇教导