bzoj 1877: [SDOI2009]晨跑 (网络流)

明显拆点费用流;

type
arr=record
toward,next,cap,cost:longint;
end; const
mm=<<;
maxn=;
maxm=; var
edge:array[..maxm]of arr;
first,slack,d:array[..maxn]of longint;
chose:array[..maxn]of boolean;
s,t,n,m,tot,esum,maxflow,maxcost:longint; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure add(i,j,k,l:longint);
begin
inc(esum);
edge[esum].toward:=j;
edge[esum].next:=first[i];
first[i]:=esum;
edge[esum].cap:=k;
edge[esum].cost:=l;
end; procedure addedge(i,j,k,l:longint);
begin
add(i,j,k,l);
add(j,i,,-l);
end; function aug(x,flow:longint):longint;
var
now,more,i,too,value:longint;
begin
if x=t then begin
inc(maxflow,flow);
inc(maxcost,flow*d[s]);
exit(flow);
end;
now:=;
chose[x]:=true;
i:=first[x];
while i>= do begin
too:=edge[i].toward;
value:=edge[i].cost;
if (edge[i].cap>) and (not chose[too]) then
if d[x]=d[too]+value then begin
more:=aug(too,min(edge[i].cap,flow-now));
dec(edge[i].cap,more);
inc(edge[i xor ].cap,more);
inc(now,more);
if flow=now then exit(flow);
end
else
slack[too]:=min(slack[too],d[too]+value-d[x]);
i:=edge[i].next;
end;
exit(now);
end; function rel:boolean;
var
i,spent:longint;
begin
spent:=maxlongint;
for i:= to tot do
if not chose[i] then spent:=min(spent,slack[i]);
if spent>=mm then exit(false);
for i:= to tot do
if chose[i] then inc(d[i],spent);
exit(true);
end; procedure into;
var
i,j,k,l:longint;
begin
esum:=-;
fillchar(first,sizeof(first),);
readln(n,m);
s:=;
t:=n<<;
tot:=t;
for i:= to n- do
addedge(i<<-,i<<,,);
addedge(,,maxlongint,);
addedge(n<<-,n<<,maxlongint,);
for i:= to m do begin
readln(j,k,l);
addedge(j<<,k<<-,,l);
end;
fillchar(d,sizeof(d),);
end; begin
into;
maxcost:=;
maxflow:=;
repeat
fillchar(slack,sizeof(slack),$7f);
repeat
fillchar(chose,sizeof(chose),false);
until aug(s,maxlongint)<=;
until not rel;
writeln(maxflow,' ',maxcost);
end.
上一篇:React Hooks使用避坑指南


下一篇:关于 unsigned int 比较大小