jiry_2's Blog

类似于那道BZOJ1221软件开发，把每天拆成两个，分别记为Xi，Yi，从S向Yi连一条流量Ai，费用为0的边。从Yi向Yi+1连一条流量maxint。对于每一个医院从Yi向Xi+Dk+1连一条流量为maxint，费用为Qk的边。从Xi向T连一条流量为k，费用为0的边。再对于每个大学都建一个节点Mi，从Mi向X1连一条流量为maxint，费用为Pi的边，从S向Mi连一条流量为Li，费用为0的边。这个网络的最小费用最大流的费用就是答案。开始数组开太大，估计是fillchar花了太多时间就T了。后来把数组改小就A了。

program p3280;
    const
        maxn=1000000000;
		modd=100000;
    type
        bian=record
            next,point,w,f:longint;
        end;
    var
		ii,t,tt,i,j,n,m,k,len,totpoint,totflow,totw,totnum:longint;
        a,l,pp,q,d:array[1..10000] of longint;
        b:array[0..200000] of bian;
        p,after,dis:array[0..10000] of longint;
        x:array[1..100000] of longint;
        pd:array[0..10000] of boolean;
    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].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
            head,i,j,now:longint;
        begin
            fillchar(x,sizeof(x),0);
            fillchar(pd,sizeof(pd),false);
            fillchar(dis,sizeof(dis),$3f);
            fillchar(after,sizeof(after),-1);
            x[1]:=0; head:=1; now:=0; pd[0]:=true; dis[0]:=0;
            while head<>now do begin
                now:=now mod modd+1;
                i:=p[x[now]];
                while i<>-1 do begin
                    j:=b[i].point;
                    if (b[i].f>0) and (b[i].w+dis[x[now]]<dis[j]) then begin
                        dis[j]:=b[i].w+dis[x[now]];
                        after[j]:=i;
                        if pd[j]=false then begin
                            pd[j]:=true;
                            head:=head mod modd+1;
                            x[head]:=j;
                        end;
                    end;
                    i:=b[i].next;
                end;
                pd[x[now]]:=false;
            end;
            if after[totpoint]>-1 then exit(true) else exit(false);
        end;
    function change:longint;
        var
            k,ans,tot,num,i,j:longint;
        begin
            i:=totpoint; j:=after[i]; k:=maxn;
            while j<>-1 do begin
                k:=min(k,b[j].f);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            ans:=0; i:=totpoint; j:=after[i];
            while j<>-1 do begin
                ans:=ans+k*b[j].w;
                dec(b[j].f,k);
                inc(b[j xor 1].f,k);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            totflow:=totflow+k;
            exit(ans);
        end;
    function dinic:longint;
        var
            ans:longint;
        begin
            ans:=0;
            while spfa do
                ans:=ans+change;
            exit(ans);
        end;
    begin
        readln(t);
        for tt:=1 to t do begin
            totnum:=0;
            readln(n,m,k);
            len:=-1;
            fillchar(p,sizeof(p),-1);
            fillchar(b,sizeof(b),0);
            for i:=1 to n do begin
                read(a[i]);
                totnum:=totnum+a[i];
            end;
            for i:=1 to m do
                read(l[i],pp[i]);
            for i:=1 to k do
                read(d[i],q[i]);
			for i:=m+1 to m+n-1 do
				add(i,i+1,maxn,0);
            for i:=1 to m do begin
                add(0,i,l[i],0);
				add(i,m+1,maxn,pp[i]);
            end;
            for i:=1 to n do begin
                add(0,i+n+m,a[i],0);
                for j:=1 to k do
                    if i+d[j]+1<=n then
						add(i+n+m,m+i+d[j]+1,maxn,q[j]);
            end;
            totpoint:=n+n+m+1;
            for i:=1 to n do
                add(m+i,totpoint,a[i],0);
            totflow:=0;
            totw:=dinic;
            if totflow<totnum then
                writeln('Case ',tt,': impossible')
            else
                writeln('Case ',tt,': ',totw);
        end;
    end.

表示再一次没节操的看了题解。假设每一天的需求量是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.

赤果果的费用流，一下子就想出来了。类似于最少路径覆盖，但是要用费用流。由于保证可以一遍覆盖，那么就费用流也就保证是一条路径覆盖所有的点。这样的话就是最小路径覆盖的加强版。把每个点拆成两个点。如果I到J有一条边就往I1向J2连一条费用为时间，流量为1的边，由源向每个I1，每个I2向汇连一条费用为0流量为1的边，它的费用流结果就是答案。开始我很SB的把瞬移都当成边连进去，然后就T得一塌糊涂，其实只要从源向每个I2连一条流量为1费用为瞬移时间的边即可，简单粗暴，就AC了。

program p1927;
	type
		bian=record
			f,w,point,next:longint;
		end;
	var
		b:array[0..4000000] of  bian;
		p,after,d,t:array[-1..5000] of longint;
		x:array[1..500000] of longint;
		pd:array[-1..5000] of boolean;
		n,m,i,j,len,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].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 min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function change:longint;
		var
			i,j,num,k:longint;
		begin
			i:=2*n+1; j:=after[i]; k:=maxlongint;
			while j<>-1 do begin
				k:=min(k,b[j].f);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			i:=2*n+1; j:=after[i]; num:=0;
			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 spfa:boolean;
		var
			head,now,i,j:longint;
		begin
			fillchar(after,sizeof(after),-1);
			fillchar(pd,sizeof(pd),false);
			fillchar(d,sizeof(d),$3f);
			head:=1; now:=0;
			x[1]:=0; pd[0]:=true; d[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (d[j]>d[x[now]]+b[i].w) and (b[i].f>0) 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[2*n+1]=-1 then exit(false) else exit(true);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while spfa do
				num:=num+change;
			exit(num);
		end;
	begin
		readln(n,m);
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			read(t[i]);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			if k1<k2 then add(k1,k2+n,1,k3) else add(k2,k1+n,1,k3);
		end;
		for i:=1 to n do
			add(0,i+n,1,t[i]);
		for i:=0 to n do
			add(0,i,1,0);
		for i:=n+1 to n*2 do
			add(i,n*2+1,1,0);
		writeln(dinic);
	end.

蛋疼的网络流，想了一会儿没思路看题解了。由于模型转换太神奇，自己百度。我这儿就贴代码了。

program p2597;
	type
		bian=record
			next,point,f,w:longint;
		end;
	var
		b:array[0..100000] of bian;
		p,d,inw,after:array[0..10000] of longint;
		pd:array[0..20000] of boolean;
		bi:array[1..200,1..200] of longint;
		x:array[1..500000] of longint;
		k,len,n,long,i,j: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,head,now:longint;
		begin
			fillchar(after,sizeof(after),-1);
			fillchar(pd,sizeof(pd),false);
			fillchar(d,sizeof(d),$3f);
			head:=1; now:=0; pd[0]:=true; x[1]:=0; d[0]:=0;
			while head<>now do begin
				now:=now+1;
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (d[x[now]]+b[i].w<d[j]) and (b[i].f>0) then begin
						d[j]:=d[x[now]]+b[i].w;
						after[j]:=i;
						if pd[j]=false then begin
							pd[j]:=true;
							head:=head+1;
							x[head]:=j;
						end;
					end;
					i:=b[i].next;
				end;
				pd[x[now]]:=false;
			end;
			if after[n*(n-1) div 2+n+1]=-1 then exit(false) else exit(true);
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function change:longint;
		var
			i,j,k,ans,num:longint;
		begin
			i:=n*(n-1) div 2+n+1; j:=after[i]; k:=maxlongint;
			while j<>-1 do begin
				k:=min(k,b[j].f);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			i:=n*(n-1) div 2+n+1; j:=after[i]; num:=0;
			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:longint;
		var
			ans:longint;
		begin
			ans:=0;
			while spfa=true do
				ans:=ans+change;
			exit(ans);
		end;
	function find(k:longint):longint;
		var
			i,j:longint;
		begin
			i:=p[k];
			while i<>-1 do begin
				if (b[i].f=0) then exit(b[i].point);
				i:=b[i].next;
			end;
		end;
	begin
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),-1);
		fillchar(inw,sizeof(inw),0);
		len:=-1;
		readln(n); long:=0;
		for i:=1 to n do
			for j:=1 to n do begin
				read(k);
				if i>=j then continue;
				inc(long);
				if k=0 then begin
					add(long,n*(n-1) div 2+i,1,0);
					inc(inw[i]);
				end else if k=1 then begin
					add(long,n*(n-1) div 2+j,1,0);
					inc(inw[j]);
				end else if k=2 then begin
					add(long,n*(n-1) div 2+i,1,0);
					add(long,n*(n-1) div 2+j,1,0);
					inc(inw[i]); inc(inw[j]);
				end;
			end;
		for i:=1 to n do
			for j:=1 to inw[i] do
				add(n*(n-1) div 2+i,n*(n-1) div 2+n+1,1,j*2-1);
		for i:=1 to n*(n-1) div 2 do
			add(0,i,1,0);
		writeln((n*(n-1)*(n-2) div 3+n*(n-1) div 2-dinic) div 2);
		long:=0;
		fillchar(bi,sizeof(bi),0);
		for i:=1 to n do
			for j:=i+1 to n do begin
				inc(long);
				if find(long)-n*(n-1) div 2=i then bi[i,j]:=0 else bi[i,j]:=1;
				bi[j,i]:=1-bi[i,j];
			end;
		for i:=1 to n do begin
			for j:=1 to n do
				write(bi[i,j],' ');
			writeln;
		end;
	end.

把每天拆成两个，分别记为Xi，Yi，从S向Xi连一条流量为maxint，费用为f的边。从S向Yi连一条流量ni，费用为0的边。从Yi向Yi+1连一条流量maxint，费用为0的边（最开始做没连这个，直接连到X去，连了好多的边，所以一直TLE）。从Yi向Xi+a连一条流量为maxint，费用为fa的边。从Yi向Xi+b连一条流量为maxint，费用为fb的边。从Xi向T连一条流量为k，费用为0的边。这个网络的最小费用最大流的费用就是答案。

program p1221;
	const
		maxn=100000000;
	type
		bian=record
			next,f,w,point:longint;
		end;
	var
		p,d,after:array[0..5000] of longint;
		pd:array[0..5000] of boolean;
		x:array[1..400000] of longint;
		b:array[0..1500000] of bian;
		len,i,j,n,a,c,f,fa,fb,k: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].f:=k4;
			b[len].w:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,-k3,0);
		end;
	function spfa:boolean;
		var
			head,i,j,now:longint;
		begin
			fillchar(x,sizeof(x),0);
			fillchar(pd,sizeof(pd),false);
			fillchar(d,sizeof(d),$3f);
			fillchar(after,sizeof(after),-1);
			x[1]:=0; head:=1; now:=0; pd[0]:=true; d[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;{
					writeln(b[i].f,' ',b[i].w+d[x[now]],' ',d[j]);
					readln;}
					if (b[i].f>0) and (b[i].w+d[x[now]]<d[j]) then begin
						d[j]:=b[i].w+d[x[now]];
						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;{
			for i:=1 to n do
				write(d[i],' ');
			readln;}
			if after[n+1]>-1 then exit(true) else exit(false);
		end;
	function change:longint;
		var
			k,ans,tot,num,i,j:longint;
		begin
			i:=n+1; j:=after[i]; k:=maxn;
			while j<>-1 do begin
				k:=min(k,b[j].f);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			ans:=0; i:=n+1; j:=after[i];
			while j<>-1 do begin
				ans:=ans+k*b[j].w;
				dec(b[j].f,k);
				inc(b[j xor 1].f,k);
				i:=b[j xor 1].point;
				j:=after[i];
			end;{
			writeln(k,' ',ans);
		readln;	}
			exit(ans);
		end;
	function dinic:longint;
		var
			ans:longint;
		begin
			ans:=0;
			while spfa do
				ans:=ans+change;
			exit(ans);
		end;
	begin
		readln(n,a,c,f,fa,fb);
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			add(0,i,f,maxn);
		for i:=1 to n-1 do
			add(n+i,n+i+1,0,maxn);
		for i:=1 to n-a-1 do
			add(n+i,i+a+1,fa,maxn);
		for i:=1 to n-c-1 do
			add(n+i,i+c+1,fb,maxn);
		for i:=1 to n do begin
			read(k);
			add(i,n*2+1,0,k);
			add(0,n+i,0,k);
		end;
		n:=n*2;
		writeln(dinic);
		{readln;
		readln;}
	end.

program p2661;
	type
		bian=record
			next,point,w,f:longint;
		end;
	var
		d,p,after:array[0..5000] of longint;
		x:array[1..500000] of longint;
		pd:array[0..5000000] of boolean;
		b:array[0..40000] of bian;
		tot,len,a,c,i,j: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 gcd(k1,k2:longint):longint;
		begin
			if k2=0 then exit(k1);
			exit(gcd(k2,k1 mod k2));
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function spfa:boolean;
		var
			head,now,i,j:longint;
		begin
			head:=1; now:=0;
			fillchar(pd,sizeof(pd),false);
			fillchar(after,sizeof(after),-1);
			fillchar(x,sizeof(x),0);
			fillchar(d,sizeof(d),$3f);
			x[1]:=0; d[0]:=0; pd[0]:=true;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (d[j]>d[x[now]]+b[i].w) and (b[i].f>0) 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]]:=true;
			end;
			if after[c+1]=-1 then exit(false) else exit(true);
		end;
	function change:longint;
		var
			num,ans,i,j:longint;
		begin
			ans:=maxlongint;
			i:=c+1; j:=after[i];
			while j<>-1 do begin
				ans:=min(b[j].f,ans);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			num:=0; i:=c+1; j:=after[i];
			tot:=tot+ans;
			while j<>-1 do begin
				num:=num+ans*b[j].w;
				dec(b[j].f,ans);
				inc(b[j xor 1].f,ans);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			exit(num);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while spfa=true do
				num:=num+change;
			exit(num);
		end;
	function max(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k2) else exit(k1);
		end;
	begin
		readln(a,c);
		len:=-1;
		tot:=0;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		for i:=a to c do
			for j:=a to c do
				if (trunc(sqrt(abs(i*i-j*j)))=sqrt(abs(i*i-j*j))) and (i<>j) then begin
					if gcd(trunc(sqrt(abs(i*i-j*j))),min(i,j))=1 then
						add(i,c+j,1,-i-j);
				end;
		for i:=a to c do begin
			add(0,i,1,0);
			add(i+c,c*2+1,1,0);
		end;
		c:=c*2;
		i:=-dinic;
		writeln(tot div 2,' ',i div 2);
	end.

把所有点拆成两个，做一次gcd，把所有满足条件之间的点连上边，构成一个二分图，流量为1，费用为-（x+y），求这个图的最小费用最大流，费用取反然后均除以2即可。

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

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.