bzoj3275

容易想到是最小割（最大权独立集）
然后每个数拆成两个点，不能同时选的之间连边跑最小割，
最后答案=总数-mincut/2 因为这样建图将流量变成了原来的两倍

当然这道题更好的建图方法是分成奇数和偶数两个集合
不难发现，奇数和奇数，偶数和偶数之间显然不能同时满足条件的
所以这样直接ans=总点数-mincut

  1 const inf=100000007;
  2 type node=record
  3        point,flow,next:longint;
  4      end;
  5 
  6 var edge:array[0..2000010] of node;
  7     a,p,cur,pre,d,numh,h:array[0..6010] of longint;
  8     s,i,j,n,t,len:longint;
  9     x:double;
 10 
 11 function gcd(a,b:longint):longint;
 12   begin
 13     if b=0 then exit(a)
 14     else exit(gcd(b,a mod b));
 15   end;
 16 
 17 function min(a,b:longint):longint;
 18   begin
 19     if a>b then exit(b) else exit(a);
 20   end;
 21 
 22 procedure add(x,y,f:longint);
 23   begin
 24     inc(len);
 25     edge[len].point:=y;
 26     edge[len].flow:=f;
 27     edge[len].next:=p[x];
 28     p[x]:=len;
 29   end;
 30 
 31 function sap:longint;
 32   var q,u,i,j,neck,tmp:longint;
 33   begin
 34     sap:=0;
 35     u:=0;
 36     numh[0]:=t+1;
 37     for i:=0 to t do
 38       cur[i]:=p[i];
 39     neck:=inf;
 40     while h[0]<t+1 do
 41     begin
 42       d[u]:=neck;
 43       i:=cur[u];
 44       while i<>-1 do
 45       begin
 46         j:=edge[i].point;
 47         if (edge[i].flow>0) and (h[u]=h[j]+1) then
 48         begin
 49           pre[j]:=u;
 50           cur[u]:=i;
 51           neck:=min(neck,edge[i].flow);
 52           u:=j;
 53           if u=t then
 54           begin
 55             sap:=sap+neck;
 56             while u<>0 do
 57             begin
 58               u:=pre[u];
 59               j:=cur[u];
 60               dec(edge[j].flow,neck);
 61               inc(edge[j xor 1].flow,neck);
 62             end;
 63             neck:=inf;
 64           end;
 65           break;
 66         end;
 67         i:=edge[i].next;
 68       end;
 69       if i=-1 then
 70       begin
 71         dec(numh[h[u]]);
 72         if numh[h[u]]=0 then exit;
 73         tmp:=t;
 74         i:=p[u];
 75         q:=-1;
 76         while i<>-1 do
 77         begin
 78           j:=edge[i].point;
 79           if edge[i].flow>0 then
 80             if h[j]<tmp then
 81             begin
 82               tmp:=h[j];
 83               q:=i;
 84             end;
 85           i:=edge[i].next;
 86         end;
 87         h[u]:=tmp+1;
 88         inc(numh[h[u]]);
 89         cur[u]:=q;
 90         if u<>0 then
 91         begin
 92           u:=pre[u];
 93           neck:=d[u];
 94         end;
 95       end;
 96     end;
 97   end;
 98 
 99 begin
100   len:=-1;
101   fillchar(p,sizeof(p),255);
102   readln(n);
103   t:=2*n+1;
104   for i:=1 to n do
105   begin
106     read(a[i]);
107     add(0,i,a[i]);
108     add(i,0,0);
109     add(i+n,t,a[i]);
110     add(t,i+n,0);
111     s:=s+a[i];
112   end;
113   for i:=1 to n-1 do
114     for j:=i+1 to n do
115     begin
116       x:=sqrt(sqr(a[i])+sqr(a[j]));
117       if (gcd(a[i],a[j])=1) and (x=trunc(x)) then
118       begin
119         add(i,j+n,inf);
120         add(j+n,i,0);
121         add(j,i+n,inf);
122         add(i+n,j,0);
123       end;
124     end;
125   writeln(s-sap div 2);
126 end.

View Code