9
9
2013
0

【BZOJ1061】【Noi2008】志愿者招募【费用流】

表示再一次没节操的看了题解。假设每一天的需求量是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.
Category: 费用流 | Tags: | Read Count: 995

登录 *


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