jiry_2's Blog

开始把题目看错了，然后就在纠结要不要拆点。后来仔细一看，发现是‘同时满足’，然后便是赤果果的最小割了。把所有数分成奇数和偶数两组，因为奇数之间不满足1，偶数之间不满足2.然后从源点向偶数连流量为其大小的边，从奇数向汇连流量为其大小的边。如果奇数和偶数之间不能同时选那么就连一条流量无穷大的边。这样做出来的最小割满足矛盾的点对中只选一个，而且其流量就是要舍弃的数字的大小和。于是乎我们用总权值把最小割减减掉即可。

program p3275;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		b:array[0..500000] of bian;
		p,dst,x,s:array[0..5000] of longint;
		pd:array[0..5000] of boolean;
		len,n,i,j,tot:longint;
	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 change(k1,k2:longint):longint;
		var
			i,j,k,num:longint;
		begin
			if (k1=n+1) or (k2=0) then exit(k2);
			num:=0;
			i:=p[k1];
			while i<>-1 do begin
				j:=b[i].point;
				if (b[i].f>0) and (dst[j]=dst[k1]+1) then begin
					k:=change(j,min(k2,b[i].f));
					k2:=k2-k; num:=num+k;
					dec(b[i].f,k); inc(b[i xor 1].f,k);
					if k2=0 then break;
				end;
				i:=b[i].next;
			end;
			if num=0 then dst[k1]:=-1;
			exit(num);
		end;
	function bfs:boolean;
		var
			i,j,head,now:longint;
		begin
			fillchar(dst,sizeof(dst),-1);
			fillchar(pd,sizeof(pd),false);
			head:=1; now:=0; pd[0]:=true; s[1]:=0; dst[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[s[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (pd[j]=false) and (b[i].f>0) then begin
						dst[j]:=dst[s[now]]+1;
						pd[j]:=true;
						if j=n+1 then exit(true);
						inc(head);
						s[head]:=j;
					end;
					i:=b[i].next;
				end;
			end;
			exit(pd[n+1]);
		end;
	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 dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while bfs=true do 
				num:=num+change(0,maxlongint);
			exit(num);
		end;
	begin
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		readln(n);
		tot:=0;
		for i:=1 to n do begin
			read(x[i]);
			tot:=tot+x[i];
		end;
		for i:=1 to n do 
			for j:=1 to n do
				if (x[i] mod 2=0) and (x[j] mod 2=1) and (trunc(sqrt(x[i]*x[i]+x[j]*x[j]))=sqrt(x[i]*x[i]+x[j]*x[j])) and (gcd(x[i],x[j])=1) then
					add(i,j,maxlongint);
		for i:=1 to n do 
			if x[i] mod 2=0 then add(0,i,x[i]) else add(i,n+1,x[i]);
		writeln(tot-dinic);
	end.