7
31
2013
1

【BZOJ2424】【HAOI2010】订货【费用流】

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







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.
Category: 费用流 | Tags: | Read Count: 1456
Avatar_small
model-paper.com 说:
2023年5月19日 18:37

Modelpapers works on giving out better service in different forms and we do not sell or giveaway your personal information other than public info giving out by you. We are very conscious about mail spam and we try to protect every email as much as possible. In certain cases your mail may be exposed to public. model-paper.com


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com