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

  1. 【BZOJ-3275&amp;3158】Number&amp; That was a close call Minimum cut

    3275: Number Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 748  Solved: 316[Submit][Status][Discus ...

  2. 【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 ...

  3. 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 ...

  4. [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 ...

  5. [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 ...

  6. 【 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 ...

  7. 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 ...

  8. bzoj3275: Number( Minimum cut )

    3275: Number subject : Portal Answer key : Double the experience @bzoj3158 Code : #include<cstdio> #include<cstring> #include< ...

  9. Bipartite graph &amp; Network flow &amp; 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

  1. -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 ...

  2. 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 ...

  3. ( 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 ...

  4. 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  ...

  5. 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 ...

  6. youku DEMO

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

  7. 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 ...

  8. 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 ...

  9. 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 ...

  10. 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 ...