7
31
2013
0

【BZOJ2539】【Ctsc2000】丘比特的烦恼【KM】

很裸的KM算法,但是数据极其恶心。调了我好几个月才A掉(一开始在VIJOS做,然后跳过,今天重新开始做),要注意的是后面输入的缘分值可能为0,所以要把不能射箭两个人之间连上-maxlongint的边,不能连0。还有就是坐标可能不是整数,应当用浮点型存储。

 



program p2539;
	type
		people=record
			na:string;
			xx,yy:extended;
		end;
    var
        x,y,aimy:array[1..100] of longint;
        vx,vy:array[1..100] of boolean;
        w:array[1..100,1..100] of longint;
		p:array[1..200] of people;
        n,m,i,j,k,a,b,c:longint;
		d:extended;
		ss,s:string;
    function max(k1,k2:extended):extended;
        begin
            if k1<k2 then exit(k2) else exit(k1);
        end;
    function min(k1,k2:extended):extended;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    function find(k:longint):boolean;
        var
            i,j,kk:longint;
        begin
			if k=0 then exit(false);
            vx[k]:=true;
            for i:=1 to n do
                if (vy[i]=false) and (x[k]+y[i]=w[k,i]) then begin
                    vy[i]:=true; 
                    if (aimy[i]=0) or (find(aimy[i])) then begin
						aimy[i]:=k;
                        exit(true);
                    end;
                end;
			exit(false);
        end;
    begin
		readln(d);
        readln(n);
        for i:=1 to 2*n do begin
			readln(s);
			j:=1;
			while (s[j+1]<>' ') do 
				inc(j);
			val(copy(s,1,j),p[i].xx,a);
			j:=j+2;
			k:=1;
			while (s[j+k]<>' ') do 
				inc(k);
			val(copy(s,j,k),p[i].yy,a);
			p[i].na:=copy(s,j+k+1,length(s)-j-k);
			for j:=1 to length(p[i].na) do 
				p[i].na[j]:=upcase(p[i].na[j]);
		end;
		readln(s);
		for i:=1 to n do
			for j:=1 to n do
				w[i,j]:=1;
		while s<>'End' do begin
			i:=1;
			k:=1;
			while s[i+k]<>' ' do
				inc(k);
			ss:=copy(s,i,k);
			for j:=1 to length(ss) do
				ss[j]:=upcase(ss[j]);
			for a:=1 to 2*n do
				if ss=p[a].na then break;
			i:=i+k+1;
			k:=1;
			while s[i+k]<>' ' do
				inc(k);
			ss:=copy(s,i,k);
			for j:=1 to length(ss) do
				ss[j]:=upcase(ss[j]);
			for b:=1 to 2*n do
				if ss=p[b].na then break;
			val(copy(s,i+k+1,length(s)-i-k),c,j);
			if a>b then w[b,a-n]:=c
				else w[a,b-n]:=c;
			readln(s);
		end;
		for i:=1 to n do
			for j:=1 to n do begin
				if sqr(p[i].xx-p[j+n].xx)+sqr(p[i].yy-p[j+n].yy)>sqr(d) then begin
					w[i,j]:=-1000000000;
					continue;
				end;
				for k:=1 to n*2 do
					if (k<>i) and (k<>j+n) and ((p[i].xx-p[j+n].xx)*(p[i].yy-p[k].yy)=(p[i].yy-p[j+n].yy)*(p[i].xx-p[k].xx))then begin
						if (p[k].xx>max(p[i].xx,p[j+n].xx)) or (p[k].xx<min(p[i].xx,p[j+n].xx)) or (p[k].yy>max(p[i].yy,p[j+n].yy)) or (p[k].yy<min(p[i].yy,p[j+n].yy)) then
							continue;
						w[i,j]:=-1000000000;
						break;
					end;
			end;
		{for i:=1 to n do begin
			for j:=1 to n do
				write(w[i,j],' ');
			writeln;
		end;
}        fillchar(y,sizeof(y),0);
        fillchar(x,sizeof(x),0);
        for i:=1 to n do
            for j:=1 to n do
                x[i]:=trunc(max(x[i],w[i,j])); 
        fillchar(aimy,sizeof(aimy),0);
        for k:=1 to n do
            repeat
				{for i:=1 to n do
					write(aimy[i],' ');
				readln;}
				fillchar(vx,sizeof(vx),false);
                fillchar(vy,sizeof(vy),false);
                if find(k) then break;
                c:=1000000;
                for i:=1 to n do begin
                    if not vx[i] then continue;
                    for j:=1 to n do begin
                        if vy[j] then continue;
                        c:=trunc(min(c,x[i]+y[j]-w[i,j]));
                    end;
                end;
                for i:=1 to n do begin
                    if vx[i] then x[i]:=x[i]-c;
                    if vy[i] then y[i]:=y[i]+c;
                end;
            until false;
        a:=0;
        for i:=1 to n do
            a:=a+w[aimy[i],i];
        writeln(a);
        {for i:=1 to n do
            writeln(aimy[i],' ',w[aimy[i],i]);
        readln;
        readln;}
    end.  
Category: KM | Tags:
7
31
2013
0

【BZOJ1066】【SCOI2007】蜥蜴【最大流】

这道题是很裸的最大流,和【BZOJ1189】紧急疏散很像,不过这道题不用按照时间拆点,需要对于每个柱子拆点,在同一个柱子的两个点间连一条流量为柱子可以通过蜥蜴数的边(即高度),然后对于这张图做最大流即可。

 

program p1066;
	const
		maxn=100000000;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		p,dst:array[0..40000] of longint;
		w:array[1..50,1..50] of longint;
		x:array[1..400000] of longint;
		pd:array[0..40000] of boolean;
		b:array[0..40000] of bian;
		len,tot,x1,x2,y1,y2,i,j,n,m,d:longint;
		ch:char;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,0);
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function bfs:boolean;
		var
			k1,k2,k3,now,head,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			pd[0]:=true; head:=1; now:=0; x[1]:=0; dst[0]:=0;
			while now<head do begin
				inc(now);
				i:=p[x[now]];
				while i>-1 do begin
					k1:=b[i].point;
					{writeln(k1,' ',b[i].f);
					readln;}
					if (pd[k1]=false) and (b[i].f>0) then begin
						pd[k1]:=true;
						dst[k1]:=dst[x[now]]+1;
						if k1=n then exit(true);
						inc(head);
						x[head]:=k1;
					end;
					i:=b[i].next;
				end;
			end;	
			exit(pd[n]);
		end;
	function change(k1,k2:longint):longint;
		var
			now,i,j,k:longint;
		begin
			if (k1=n) or (k2=0) then exit(k2);
			now:=p[k1];
			j:=0;
			while now>-1 do begin
				i:=b[now].point;
				if (b[now].f>0) and (dst[k1]=dst[i]-1) then begin
					k:=change(i,min(b[now].f,k2));
					k2:=k2-k;
					j:=j+k;
					b[now].f:=b[now].f-k;
					inc(b[now xor 1].f,k);
					if k2=0 then break;
				end;
				now:=b[now].next;
			end;
			if j=0 then dst[k1]:=-1;
			exit(j);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while bfs=true do
				num:=num+change(0,maxn);
			exit(num);
		end;
	begin
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		readln(n,m,d);
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				w[i,j]:=ord(ch)-ord('0');
				if (i<=d) or (j<=d) or (i>=n-d+1) or (j>=m-d+1) then add(i*m-m+j+n*m,n*m*2+1,maxn);
			end;
			readln;
		end;
		for x1:=1 to n do 
			for y1:=1 to m do
				for x2:=1 to n do
					for y2:=1 to m do
						if ((x1<>x2) or (y1<>y2)) and (sqrt(sqr(x1-x2)+sqr(y1-y2))<=d) then 
							add(x1*m-m+y1+n*m,x2*m-m+y2,maxn);
		tot:=0;
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				if ch='L' then begin
					dec(w[i,j]);
					add(0,i*m-m+j+n*m,1);
					inc(tot);
				end;
				add(i*m-m+j,i*m-m+j+n*m,w[i,j]);
			end;
			readln;
		end;
		n:=n*m*2+1;
		writeln(tot-dinic);
	end.
Category: 最大流 | Tags:
7
31
2013
0

【BZOJ2748】【HAOI2012】音量调节【DP】

背包,不用多说了。



program p2748;
	var
		f:array[0..50,0..1000] of boolean;
		x:array[1..100] of longint;
		ans,n,maxn,i,j,k:longint;
	begin
		readln(n,ans,maxn);
		for i:=1 to n do 
			read(x[i]);
		fillchar(f,sizeof(f),false);
		f[0,ans]:=true;
		for i:=1 to n do
			for j:=0 to maxn do begin
				if (j+x[i]<=maxn) and (f[i-1,j]=true) then
					f[i,j+x[i]]:=true;
				if (j-x[i]>=0) and (f[i-1,j]=true) then 
					f[i,j-x[i]]:=true;
			end;
		j:=-1;
		for i:=maxn downto 0 do
			if f[n,i]=true then begin
				j:=i;
				break;
			end;
		writeln(j);
	end.
Category: DP | Tags:
7
31
2013
0

【BZOJ2661】【BeiJing wc2012】连连看【费用流+gcd】



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即可。

Category: 费用流 | Tags:
7
31
2013
0

【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:
7
31
2013
0

【BZOJ1266】【AHOI2006】上学路线route【最小割+最短路】



program p1266;
	type
		bian=record
			first,next,point,f,w,bo:longint;
		end;
	var
		b:array[1..1000000] of bian;
		p,d,dst:array[1..100000] of longint;
		x:array[1..1000000] of longint;
		pd:array[1..100000] of boolean;
		k1,k2,k3,k4,len,i,j,n,m:longint;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].first:=k1;
			b[len].w:=k3;
			b[len].f:=k4;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,k3,0);
		end;
	procedure spfa;
		var
			head,now,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			fillchar(x,sizeof(x),0);
			fillchar(d,sizeof(d),$3f);
			head:=1; now:=0; x[1]:=n; d[n]:=0; pd[n]:=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 then begin
						d[j]:=d[x[now]]+b[i].w;
						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;
		end;
	procedure dfs(k:longint);
		var
			i,j:longint;
		begin
			pd[k]:=true;
			if k=n then exit;
			i:=p[k];
			while i<>-1 do begin
				j:=b[i].point;
				if (d[j]+b[i].w=d[k]) and (b[i].f>0) then begin
					b[i].bo:=1;
					b[i xor 1].bo:=1;
					if pd[j]=false then dfs(j);
				end;
				i:=b[i].next;
			end;
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function bfs:boolean;
		var
			k1,k2,k3,now,head,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			pd[1]:=true; head:=1; now:=0; x[1]:=1; dst[1]:=0;
			while now<head do begin
				inc(now);
				i:=p[x[now]];
				while i>-1 do begin
					k1:=b[i].point;
					{writeln(k1,' ',b[i].f,' ',b[i].bo);
					readln;}
					if (pd[k1]=false) and (b[i].f>0) and (b[i].bo>0) then begin
						pd[k1]:=true;
						dst[k1]:=dst[x[now]]+1;
						if k1=n then exit(true);
						inc(head);
						x[head]:=k1;
					end;
					i:=b[i].next;
				end;
			end;	
			exit(pd[n]);
		end;
	function change(k1,k2:longint):longint;
		var
			now,i,j,k:longint;
		begin
			if (k1=n) or (k2=0) then exit(k2);
			now:=p[k1];
			j:=0;
			while now>-1 do begin
				i:=b[now].point;
				if (b[now].f>0) and (dst[k1]=dst[i]-1) and (b[now].bo>0) then begin
					k:=change(i,min(b[now].f,k2));
					k2:=k2-k;
					j:=j+k;
					b[now].f:=b[now].f-k;
					inc(b[now xor 1].f,k);
					if k2=0 then break;
				end;
				now:=b[now].next;
			end;
			if j=0 then dst[k1]:=-1;
			exit(j);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while bfs=true do begin
				num:=num+change(1,maxlongint);
			end;
			exit(num);
		end;
	begin
		readln(n,m);
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3,k4);
			add(k1,k2,k3,k4);
			add(k2,k1,k3,k4);
		end;
		spfa;
		writeln(d[1]);
		{for i:=1 to n do
			write(d[i],' ');
		writeln;}
		fillchar(pd,sizeof(pd),false);
		dfs(1);
		{for i:=1 to len do
			writeln(b[i].first,' ',b[i].point,' ',b[i].w,' ',b[i].bo,' ',b[i].f);}
		writeln(dinic);
	end.

先做一次SPFA,然后就可以求出家到学校的最短路图(由所有最短路构成的图),在这个图上做最小割,流量为C,答案就是正解。

Category: 最大流 | Tags:
7
31
2013
0

【BZOJ1189】【HNOI2007】紧急疏散evacuate【最大流】

一道网络流的题目。二分时间,然后把每个出口按照时间拆点,每个人向可以到达门的最短时间以后的门节点连一条流量为1的边。源点到所有人连一条流量为1的边,所有门向汇连一条流量为1的边,如果最大流是人的总数则可以逃离,向下二分。



program p1189;
	const
		h:array[1..4] of longint=(0,1,0,-1);
		z:array[1..4] of longint=(1,0,-1,0);	
	type
		bian=record
			point,next,f:longint;
		end;
		arr=array[1..400] of longint;
	var
		y:array[0..21,0..21] of longint;
		x,s,p,dst:array[0..400000] of longint;
		pd:array[1..400000] of boolean;
		b:array[0..2000000] of bian;
		d:array[1..800] of arr;
		maxn,last,mid,ans,l,r,q,k1,k2,k,long,len,tot,n,m,i,j:longint;
		ch:char;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,0);
		end;
	procedure bfs1(k:longint;var d:arr);
		var
			i,j,head,now:longint;
		begin
			fillchar(s,sizeof(s),0);
			fillchar(pd,sizeof(pd),false);
			head:=1; now:=0; s[1]:=x[k]; d[x[k]]:=0; pd[x[k]]:=true;
			while head>now do begin
				inc(now);
				i:=p[s[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (pd[j]=false) then begin
						inc(head);
						pd[j]:=true;
						s[head]:=j;
						d[j]:=d[s[now]]+1;
					end;
					i:=b[i].next;
				end;
			end;
		end;
	function bfs:boolean;
		var
			k1,k2,k3,now,head,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			pd[0]:=true; head:=1; now:=0; s[1]:=0; dst[0]:=0;
			while now<head do begin
				inc(now);
				i:=p[s[now]];
				while i>-1 do begin
					k1:=b[i].point;
					if (pd[k1]=false) and (b[i].f>0) then begin
						pd[k1]:=true;
						dst[k1]:=dst[s[now]]+1;
						if k1=last then exit(true);
						inc(head);
						s[head]:=k1;
					end;
					i:=b[i].next;
				end;
			end;	
			exit(pd[last]);
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function change(k1,k2:longint):longint;
		var
			now,i,j,k:longint;
		begin
			if (k1=last) or (k2=0) then exit(k2);
			now:=p[k1];
			j:=0;
			while now>-1 do begin
				i:=b[now].point;
				if (b[now].f>0) and (dst[k1]=dst[i]-1) then begin
					k:=change(i,min(b[now].f,k2));
					k2:=k2-k;
					j:=j+k;
					b[now].f:=b[now].f-k;
					inc(b[now xor 1].f,k);
					if k2=0 then break;
				end;
				now:=b[now].next;
			end;
			if j=0 then dst[k1]:=-1;
			exit(j);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while bfs do 
				num:=num+change(0,maxlongint);
			exit(num);
		end;
	function find(t:longint):boolean;
		var
			q,k,k1,k2,i,j:longint;
		begin
			k:=long*t;
			fillchar(p,sizeof(p),-1);
			fillchar(b,sizeof(b),0);
			len:=-1;
			for i:=1 to long do
				for j:=1 to n*m do begin
					if y[(j-1) div m+1,(j-1) mod m+1]=2 then continue;
					for q:=d[i,j] to t do begin
						k1:=q*long-long+i;
						k2:=k+j;
					{	WRITELN(K1,' ',K2,' ',LONG,' ',Q);}
						add(k2,k1,1);
					end;
				end;
			for i:=1 to k do
				add(i,k+n*m+1,1);
			last:=k+n*m+1;
			for i:=k+1 to n*m+k do
				add(0,i,1);
			if dinic=tot then exit(true) else exit(false);
		end;
	begin
		readln(n,m);
		fillchar(y,sizeof(y),0);
		long:=0;
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				if ch='.' then y[i,j]:=1
					else if ch='D' then begin
						inc(long);
						x[long]:=i*m-m+j;
						y[i,j]:=2;
					end;
			end;
			readln;
		end;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			for j:=1 to m do 
				for k:=1 to 4 do begin
					k1:=i+h[k];
					k2:=j+z[k];
					if (y[i,j]<>0) and (y[k1,k2]<>0) then begin
						ade(i*m-m+j,k1*m-m+k2,1);
						ade(k1*m-m+k2,i*m-m+j,1);
					end;
				end;
		fillchar(d,sizeof(d),$3f);
		maxn:=d[1,1];
		for i:=1 to long do
			bfs1(i,d[i]);
		l:=0;
		for i:=1 to long do
			for j:=1 to n*m do
				if (l<d[i,j]) and (d[i,j]<>maxn) then l:=d[i,j];
		r:=0;
		for i:=1 to n do
			for j:=1 to m do
				if y[i,j]=1 then inc(r);
		tot:=r; 
		r:=r+l+1;
		l:=1;
		if find(r)=false then begin
			write('impossible');
			exit;
		end;
		while r>l do begin
			mid:=(r+l) div 2;
			if find(mid) then begin
				r:=mid;
				ans:=mid;
			end else
				l:=mid+1;
		end;
		writeln(ans);
	end.
Category: 最大流 | Tags:
7
30
2013
0

【BZOJ1935】【Shoi2007】Tree 园丁的烦恼【离散化+树状数组】

为了求矩形中的点的数量,首先可以想到的就是二维线段树或者二维树状数组,但是这道题的数据范围比较大,即使离散化之后还有200万多的点,会超空间。所以只能用一维的树状数组,可以先把所有点(包括查询矩形的四个顶点)按照第一关键字Y轴升序排序,第二关键字X轴升序排序。然后离散化,然后再扫一遍,如果是点就插入到树状数组中,如果是查询就求和,其值为右上角为改点,左下角为原点的矩形内的点,每个查询可以通过四个顶点的加减来考虑。有两点要考虑:1.要考虑边界,可以通过给点设值来排序。2.对N=0的情况要特判。

 





program p1935;
	const
		p:array[0..4] of longint=(4,1,3,5,2);
	type
		tree=record
			x,y:longint;
		end;
		num=record
			x,y,sx,pd,ls:longint;
		end;
		question=record
			x1,x2,y1,y2:longint;
			w:array[0..4] of longint;
		end;
		hzb=record	
			x,sx:longint;
		end;
	var
		t:array[1..500000] of tree;
		q:array[1..500000] of question;
		x:array[0..3000000] of num;
		h:array[0..3000000] of longint;
		c:array[1..3000000] of longint;
		len,n,m,i,j:longint;
	procedure add(k1,k2,k3,k4:longint);
		begin
			inc(len);
			x[len].x:=k1;
			x[len].y:=k2;
			x[len].sx:=k4;
			x[len].pd:=k3;
		end;
	function bo(k1,k2:longint):boolean;
		begin
			if x[k1].y<x[k2].y then exit(true);
			if x[k1].y>x[k2].y then exit(false);
			if x[k1].pd<=1 then exit(true);
			if x[k2].pd<=1 then exit(false);
			if x[k1].x<x[k2].x then exit(true);
			if x[k1].x>x[k2].x then exit(false);
			if x[k1].pd<=x[k2].pd then exit(true);
			exit(false);
		end;
	procedure quick(first,en:longint);
		var
			i,j:longint;
		begin
			{writeln(first,' ',en);}
			i:=first; j:=en; x[0]:=x[first];
			while i<j do begin
				{writeln(x[i].x,' ',x[i].y,' ',x[i].pd);
				writeln(x[j].x,' ',x[j].y,' ',x[j].pd);
				writeln(x[0].x,' ',x[0].y,' ',x[0].pd);}
				while (i<j) and (bo(0,j)=true) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (bo(i,0)=true) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then quick(first,i-1);
			if i<en-1 then quick(i+1,en);
		end;
	procedure sort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; h[0]:=h[i];
			while i<j do begin
				while (i<j) and ((x[h[j]].x>x[h[0]].x) or ((x[h[j]].x=x[h[0]].x)) and (p[x[h[j]].pd]>=p[x[h[0]].pd])) do dec(j);
				if i<j then h[i]:=h[j];
				while (i<j) and ((x[h[i]].x<x[h[0]].x) or ((x[h[i]].x=x[h[0]].x)) and (p[x[h[i]].pd]<p[x[h[0]].pd])) do inc(i);
				if i<j then h[j]:=h[i];
			end;
			h[i]:=h[0];
			if i>first+1 then sort(first,i-1);
			if i<en-1 then sort(i+1,en);
		end;
	function lowbit(k:longint):longint;
		begin
			exit(k and -k);
		end;
	procedure add(k:longint);
		var
			i,j:longint;
		begin
			i:=k;
			while i<=len do begin
				inc(c[i]);
				i:=i+lowbit(i);
			end;
		end;
	function total(k:longint):longint;
		var
			i,j,num:longint;
		begin
			i:=k; num:=0;
			while i>0 do begin
				num:=num+c[i];
				i:=i-lowbit(i);
			end;
			exit(num);
		end;
	begin
		readln(n,m); len:=0;
		fillchar(x,sizeof(x),0);
		for i:=1 to n do begin
			readln(t[i].x,t[i].y);
			add(t[i].x,t[i].y,2,i);
		end;
		if n=0 then begin
			for i:=1 to m do
				writeln(0);
			exit;
		end;
		for i:=1 to m do begin
			readln(q[i].x1,q[i].y1,q[i].x2,q[i].y2);
			add(q[i].x1,q[i].y1,1,i);
			add(q[i].x2,q[i].y2,3,i);
			add(q[i].x1,q[i].y2,4,i);
			add(q[i].x2,q[i].y1,0,i);
		end;
		quick(1,len);
		fillchar(c,sizeof(c),0);
		for i:=1 to len do
			h[i]:=i;
		sort(1,len);
		for i:=1 to len do
			x[h[i]].ls:=i;
		for i:=1 to len do
			if x[i].pd=2 then 
				add(x[i].ls)
			else 
				q[x[i].sx].w[x[i].pd]:=total(x[i].ls);
		for i:=1 to m do begin
			writeln(q[i].w[3]+q[i].w[1]-q[i].w[0]-q[i].w[4]);
		end;
	end.


Category: 数据结构 | Tags:
7
30
2013
0

【BZOJ1001】【BeiJing2006】狼抓兔子【最小割+最短路】

这道题是一道很裸最小割,但是由于数据范围太大,所以要用最短路来实现。建图比较诡异,详情看代码。



program p1001;
	type
		bian=record
			point,next,w:longint;
		end;
		d=record
			po,w:longint;
		end;
	var
		p,f:array[0..3000000] of longint;
		b:array[1..9000000] of bian;
		x:array[1..3000000] of d;
		pd:array[0..2000000] of boolean;
		maxn,k1,k2,k3,n,m,i,j,len,t1,t2:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].w:=k3;
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure charu(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function mi(k1,k2:longint):longint;
		begin
			if x[k1].w>x[k2].w then exit(k2) else exit(k1);
		end;
	function min(k1,k2,k3:longint):longint;
		begin
			exit(mi(mi(k1,k2),k3));
		end;
	procedure press(k:longint);
		var
			k1:longint;
			k2:d;
		begin
			k1:=min(k,k*2,k*2+1);
			if k1=k then exit;
			k2:=x[k1];
			x[k1]:=x[k];
			x[k]:=k2;
			press(k1);
		end;
	procedure find(k:longint);
		var
			k1:d;
		begin
			if k=1 then exit;
			if x[k div 2].w>x[k].w then begin
				k1:=x[k];
				x[k]:=x[k div 2];
				x[k div 2]:=k1;
				find(k div 2);
			end;
		end;
	function dijstra:longint;
		var
			k1,k2,k3,i,j,now,len:longint;
			k:d;
		begin
			fillchar(pd,sizeof(pd),true);
			fillchar(x,sizeof(x),$7f);
			maxn:=x[1].po; len:=1;
			fillchar(f,sizeof(f),$3f);
			x[1].po:=0; x[1].w:=0; f[0]:=0;
			while len>0 do begin
				len:=len-1;
				k:=x[1];
				if len>0 then begin
					x[1]:=x[len+1];
					x[len+1].w:=maxn;
					press(1);
				end;
				if pd[k.po]=false then continue;
				pd[k.po]:=false;
				k2:=p[k.po];
				while k2>0 do begin
					k1:=b[k2].point;
					if f[k.po]+b[k2].w<f[k1] then begin
						f[k1]:=f[k.po]+b[k2].w;
						inc(len);
						x[len].po:=k1; x[len].w:=f[k1];
						find(len);
					end;
					k2:=b[k2].next;
				end;
			end;
			exit(f[t2]);
		end;
	begin
		readln(n,m);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		t1:=(n-1)*(m-1);
		t2:=t1*2+1;
		if (n=1) and (m=1) then begin
			writeln(0);
			exit;
		end;
		for i:=1 to n do
			for j:=1 to m-1 do begin
				read(k1);
				if i=1 then k2:=0 else k2:=(i-2)*(m-1)+j+t1;
				if i=n then k3:=t2 else k3:=(i-1)*(m-1)+j;
				charu(k2,k3,k1);
			end;
		for i:=1 to n-1 do
			for j:=1 to m do begin
				read(k1);
				if j=1 then k2:=t2 else k2:=(i-1)*(m-1)+j-1;
				if j=m then k3:=0 else k3:=(i-1)*(m-1)+j+t1;
				charu(k2,k3,k1);
			end;
		for i:=1 to n-1 do
			for j:=1 to m-1 do begin
				read(k1);
				k2:=(i-1)*(m-1)+j;
				k3:=(i-1)*(m-1)+j+t1;
				charu(k2,k3,k1);
			end;
		writeln(dijstra);
	end.
				
Category: 最短路 | Tags:

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