jiry_2's Blog

很裸的费用流，不过应当注意题目描述有点问题，它是先把所有东西卖出然后再存入仓库。

program p2424;
	const
		max=10000000;
	type
		bian=record
			w,f,point,next:longint;
		end;
	var
		pd:array[0..100] of boolean;
		x:array[1..1000] of longint;
		after,d,u,l,p:array[0..100] of longint;
		b:array[0..1000] of bian;
		len,i,j,m,n,s:longint;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].w:=k4;
			b[len].f:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,0,-k4);
		end;
	function change:longint;
		var
			tot,now,i,j,k:longint;
		begin
			k:=max;
			now:=n; 
			while now>0 do begin
				i:=after[now];
				k:=min(k,b[i].f);
				now:=b[i xor 1].point;
			end;
			now:=n; tot:=0;
			while now>0 do begin
				i:=after[now];
				dec(b[i].f,k);
				inc(b[i xor 1].f,k);
				inc(tot,b[i].w*k);
				now:=b[i xor 1].point;
			end;
			exit(tot);
		end;
	function spfa:boolean;
		var
			i,j,now,head:longint;
		begin
			fillchar(x,sizeof(x),0);
			fillchar(pd,sizeof(pd),false);
			fillchar(after,sizeof(after),-1);
			fillchar(l,sizeof(l),$3f);
			head:=1; now:=0; x[1]:=0; pd[0]:=true; l[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i>-1 do begin
					j:=b[i].point;
					if (l[j]>l[x[now]]+b[i].w) and (b[i].f>0) then begin
						l[j]:=l[x[now]]+b[i].w;
						after[j]:=i;
						if pd[j]=false then begin
							inc(head);
							x[head]:=j;
							pd[j]:=true;
						end;
					end;
					i:=b[i].next;
				end;
				pd[x[now]]:=false;
			end;
			if after[n]>-1 then exit(true) else exit(false);
		end;
	function dinic:longint;
		var
			i,j,ans:longint;
		begin
			ans:=0;
			while spfa do 
				ans:=ans+change;
			exit(ans);
		end;
	begin
		readln(n,m,s);
		for i:=1 to n do
			read(u[i]);
		for i:=1 to n do
			read(d[i]);
		fillchar(p,sizeof(p),-1);
		fillchhar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			add(0,i,max,d[i]);
		for i:=1 to n-1 do
			add(i,i+1,s,m);
		for i:=1 to n do
			add(i,n+1,u[i],0);
		inc(n);
		writeln(dinic);
	end.