表示再一次没节操的看了题解。假设每一天的需求量是num[i]，令num[0]=num[n+1]=0。那么如果对于1<=i<=n+1，如果num[i]-num[i-1]>0就由S向i连一条边，反之则连到T，流量为abs(num[i]-num[i-1])，费用为0。然后对于每类志愿者从a工作到b，费用为c，就从a向b+1连一条费用为c，流量为maxlongint的边。再由i+1向i连一条流量为maxlongint费用为0的边。求最小费用最大流即可。
program p1061; type bian=record next,point,w,f:int64; end; var b:array[1..500000] of bian; d,p,after,num:array[0..2000] of int64; x:array[1..100000] of longint; pd:array[0..2000] of boolean; len,n,m,i,j,k1,k2,k3:longint; procedure ade(k1,k2,k3,k4:longint); begin inc(len); b[len].point:=k2; b[len].next:=p[k1]; b[len].f:=k3; b[len].w:=k4; p[k1]:=len; end; procedure add(k1,k2,k3,k4:longint); begin ade(k1,k2,k3,k4); ade(k2,k1,0,-k4); end; function spfa:boolean; var i,j,now,head:longint; begin fillchar(after,sizeof(after),-1); fillchar(pd,sizeof(pd),false); fillchar(d,sizeof(d),$3f); x[1]:=0; pd[0]:=true; d[0]:=0; head:=1; now:=0; while now<head do begin inc(now); i:=p[x[now]]; while i<>-1 do begin j:=b[i].point; if (b[i].f>0) and (d[x[now]]+b[i].w<d[j]) then begin d[j]:=d[x[now]]+b[i].w; after[j]:=i; if pd[j]=false then begin pd[j]:=true; inc(head); x[head]:=j; end; end; i:=b[i].next; end; pd[x[now]]:=false; end; if after[n+2]=-1 then exit(false) else exit(true); end; function min(k1,k2:int64):int64; begin if k1<k2 then exit(k1) else exit(k2); end; function change:int64; var i,j,k,num:int64; begin k:=maxlongint*50000000; i:=n+2; j:=after[i]; while j<>-1 do begin k:=min(k,b[j].f); i:=b[j xor 1].point; j:=after[i]; end; num:=0; i:=n+2; j:=after[i]; while j<>-1 do begin num:=num+k*b[j].w; inc(b[j xor 1].f,k); dec(b[j].f,k); i:=b[j xor 1].point; j:=after[i]; end; exit(num); end; function dinic:int64; var num:int64; begin num:=0; while spfa=true do num:=num+change; exit(num); end; begin readln(n,m); fillchar(num,sizeof(num),0); fillchar(b,sizeof(b),0); fillchar(p,sizeof(p),-1); len:=-1; for i:=1 to n do begin read(num[i]); if num[i]-num[i-1]>0 then add(0,i,num[i]-num[i-1],0) else add(i,n+2,num[i-1]-num[i],0); end; add(n+1,n+2,num[n],0); for i:=1 to m do begin readln(k1,k2,k3); add(k1,k2+1,maxlongint,k3); end; for i:=1 to n do add(i+1,i,maxlongint,0); writeln(dinic); end.
评论 (0)
