7
31
2013
1

【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: | Read Count: 1536
Avatar_small
Matthew Prell 说:
2019年6月03日 00:18

The programming and the making of the useful files are by the described names and the collaboration of the sense. The Jiry blog is the blog in the essaymama review with the whole review of the essay and making the essay useful in all matters.


登录 *


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