It's easy to think of the smallest cut （ Most powerful independent set ）

Then each number is divided into two points , You can't choose the minimum cut between the two sides at the same time ,

Final answer = total -mincut/2 Because in this way, the traffic is doubled

Of course, the better way to build this problem is to divide it into odd and even sets

It's not hard to find out , Odd and odd numbers , It is obvious that even numbers and even numbers cannot satisfy the conditions at the same time

So this is direct ans= Total points -mincut

const inf=;

type node=record

point,flow,next:longint;

end; var edge:array[..] of node;

a,p,cur,pre,d,numh,h:array[..] of longint;

s,i,j,n,t,len:longint;

x:double; function gcd(a,b:longint):longint;

begin

if b= then exit(a)

else exit(gcd(b,a mod b));

end; function min(a,b:longint):longint;

begin

if a>b then exit(b) else exit(a);

end; procedure add(x,y,f:longint);

begin

inc(len);

edge[len].point:=y;

edge[len].flow:=f;

edge[len].next:=p[x];

p[x]:=len;

end; function sap:longint;

var q,u,i,j,neck,tmp:longint;

begin

sap:=;

u:=;

numh[]:=t+;

for i:= to t do

cur[i]:=p[i];

neck:=inf;

while h[]<t+ do

begin

d[u]:=neck;

i:=cur[u];

while i<>- do

begin

j:=edge[i].point;

if (edge[i].flow>) and (h[u]=h[j]+) then

begin

pre[j]:=u;

cur[u]:=i;

neck:=min(neck,edge[i].flow);

u:=j;

if u=t then

begin

sap:=sap+neck;

while u<> do

begin

u:=pre[u];

j:=cur[u];

dec(edge[j].flow,neck);

inc(edge[j xor ].flow,neck);

end;

neck:=inf;

end;

break;

end;

i:=edge[i].next;

end;

if i=- then

begin

dec(numh[h[u]]);

if numh[h[u]]= then exit;

tmp:=t;

i:=p[u];

q:=-;

while i<>- do

begin

j:=edge[i].point;

if edge[i].flow> then

if h[j]<tmp then

begin

tmp:=h[j];

q:=i;

end;

i:=edge[i].next;

end;

h[u]:=tmp+;

inc(numh[h[u]]);

cur[u]:=q;

if u<> then

begin

u:=pre[u];

neck:=d[u];

end;

end;

end;

end; begin

len:=-;

fillchar(p,sizeof(p),);

readln(n);

t:=*n+;

for i:= to n do

begin

read(a[i]);

add(,i,a[i]);

add(i,,);

add(i+n,t,a[i]);

add(t,i+n,);

s:=s+a[i];

end;

for i:= to n- do

for j:=i+ to n do

begin

x:=sqrt(sqr(a[i])+sqr(a[j]));

if (gcd(a[i],a[j])=) and (x=trunc(x)) then

begin

add(i,j+n,inf);

add(j+n,i,);

add(j,i+n,inf);

add(i+n,j,);

end;

end;

writeln(s-sap div );

end.

## bzoj3275 More articles about

- 【BZOJ-3275&3158】Number& That was a close call Minimum cut
3275: Number Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 748 Solved: 316[Submit][Status][Discus ...

- 【BZOJ3275】Number Minimum cut
[BZOJ3275]Number Description Yes N A positive integer , You need to pick some numbers out of them , Make the sum of these numbers maximum . If there are two numbers a,b At the same time, the following conditions are met , be a,b Can't be selected at the same time 1: There are positive integers C, send a*a+b*b=c ...

- bzoj3275: Number
Minimum cut ... Then push to know that the case that can't be seen must be an odd even , therefore s-> p. -> accidentally ->t. Run the minimum cut . #include<cstdio> #include<cstring&g ...

- [BZOJ3275] Number ( Network flow )
Description Yes N A positive integer , You need to pick some numbers out of them , Make the sum of these numbers maximum . If there are two numbers a,b At the same time, the following conditions are met , be a,b Can't be selected at the same time 1: There are positive integers C, send a*a+b*b=c*c 2:gcd(a,b)=1 ...

- [BZOJ3275]Number Problem solving report | Network flow
Description Yes N A positive integer , You need to pick some numbers out of them , Make the sum of these numbers maximum . If there are two numbers a,b At the same time, the following conditions are met , be a,b Can't be selected at the same time 1: There are positive integers C, send a*a+b*b=c*c2:gcd(a,b)=1 This way ...

- 【 Minimum cut 】【Dinic】bzoj3275 Number
Every point, every point , Separately to the source / Huilian a[i] The edge of , The interconnection that satisfies the condition INF The edge of , The answer for sum-maxflow*2. Because if several points can't be selected at the same time , We have to greedily choose one and the largest part , This can be guaranteed by minimal cuts . #inc ...

- Number BZOJ3275 Maximum flow
Yes N A positive integer , You need to pick some numbers out of them , Make the sum of these numbers maximum . If there are two numbers a,b At the same time, the following conditions are met , be a,b Can't be selected at the same time 1: There are positive integers C, send a*a+b*b=c*c 2:gcd(a,b)=1 Sample Outp ...

- bzoj3275: Number( Minimum cut )
3275: Number subject : Portal Answer key : Double the experience @bzoj3158 Code : #include<cstdio> #include<cstring> #include< ...

- Bipartite graph & Network flow & The summary of the minimum cut and other problems
Bipartite graph Foundation : The biggest match : hungarian algorithm Minimum point coverage = The biggest match Minimum edge coverage = Total nodes - The biggest match The largest independent set = points - The biggest match Network flow : skill : 1. Take the point as the edge , That is, a point has a limit , You can turn it into an edge BZOJ1066, ...

## Random recommendation

- -Android - Thread pool Upload pictures in batches - attach php Receive code
( Source :http://www.cnblogs.com/linguanh/) Catalog : 1, Before the order 2, Class characteristics 3, usage 4,java Code 5,php Code 1, Before the order Or from refactoring , Looking at the fragments written in a hurry before ...

- About SVN Link server Unable to connect to a repository at URL* Report the wrong question
stay BAE It's managed to write code , Want to use SVN Do version control , But there's no connection between life and death , But with Dreamweave You can connect it , It's been a long time dan Painful cache problem , Just clear the cache OK 了 . TortoiseSVN->Setting-&g ...

- （ turn ： daifubing The blog of ）Delphi QR code Chinese support 、 grouping 、 Summary of batch printing experience
I haven't been exposed to any complicated reports , It's all simple reports , stay DelphI Next use QuickReport Generally, it can meet the needs , Because of the changes in the company's demand now , New requirements are put forward for bar code scanning , The main thing is to scan the code to include more content , The previous one ...

- BZOJ Tyvj 1729 Literature and art balance tree
Description You need to write a data structure ( Please refer to the title ), To maintain an ordered sequence of numbers , The following operations need to be provided : Flip an interval , For example, the original sequence is 5 4 3 2 1, The flip zone is [2,4] Words , The result is 5 2 3 ...

- FastJSON Pre application testing
FastJSON Pre application testing FastJSON It's a very good java Open source json Tool library , Compared with other similar json Class library , Its speed is really fast, The fastest ! But the documentation is not good , We have to test some functions before application .\ actual ...

- youku DEMO
http://v.youku.com/v_show/id_XMTQxOTc4ODA4OA==.html http://v.youku.com/v_show/id_XMTQxOTc5MjU1Mg==.h ...

- Python The way 3Day
3.python Basic supplement ( aggregate ,collection series , Depth copy ) One . aggregate 1. aggregate (set): Put different elements together to form a collection , yes python Basic data types . Collection elements (set elements ...

- oracle AWR Performance monitoring report generation method
At present, quite a few companies will use oracle, During the performance test , Monitoring the database is very important , So here's how to generate oracle Self contained awr Monitoring report , And the content analysis of the specific report will be put in the subsequent blog oracle Performance analysis into ...

- vs The project and msql Incompatible solutions
When vs The project loaded libmysql.lib namely : Attach include directory , Additional Library Directory , After the additional dependencies are set , If it has been compiled, it will appear as follows : error LNK2019: Unresolved external symbols _mysql_real_co ...

- CentOS7 Configuration environment
1. install CentOS Configuration environment (1) Install in virtual machine CentOS, Access to the system yum The command is not only executed normally …… reason : Network card activation needs to be set resolvent : vi /etc/sysconfig/network-scr ...