开始把题目看错了,然后就在纠结要不要拆点。后来仔细一看,发现是‘同时满足’,然后便是赤果果的最小割了。把所有数分成奇数和偶数两组,因为奇数之间不满足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.