Description

有N个正整数，需要从中选出一些数，使这些数的和最大。

若两个数a,b同时满足以下条件，则a,b不能同时被选

1:存在正整数C，使a*a+b*b=c*c

2:gcd(a,b)=1

Input

第一行一个正整数n，表示数的个数。

第二行n个正整数a1,a2,?an。

 

 

Output

最大的和。

 

Sample Input

5

3 4 5 6 7

Sample Output

22

HINT

 

n<=3000。

 

Source

 

题解：

二元组建图 ：  

先将求最大值改为负的最小费用

选了一个数x看成造成-x的费用，同时选了不能同时选的点对看成inf的费用

然后发现K值是负的，那么这个图有没有二分图性质呢

答案显然是有的（不然有这题干什么）

若存在正整数a，b，c，满足a

²+b

²=c

²，且a，b互质，那么a和b的奇偶性不同

证明：正整数显然表示成4k，4k+1，4k+2，4k+3中的一种

而 (4k)

² mod 4 = 0

(4k+1)

² mod 4 = 1

(4k+2)

² mod 4 = 0

(4k+3)

² mod 4 = 1

 

显然 (a² mod 4)+(b² mod 4)=(c² mod 4) 

1. c如果为 4k 或 4k+2，只有a² mod 4和b² mod 4都是0才有可能满足上式，但这不满足a，b互质的要求（显然a和b此时都是偶数）

2. c如果为 4k+1 或 4k+3，a² mod 4和b² mod 4不能同为0或1，此时a，b的奇偶性不同

所以只有可能在一对奇偶不同的数才由可能建边，所以这个图有二分图性质

code：

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #define maxn 3005 7 #define maxm 6000000 8 #define inf 1061109567 9 using namespace std;10 char ch;11 bool ok;12 void read(int &x){13     for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;14     for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());15     if (ok) x=-x;16 }17 int n,a[maxn],sum;18 struct flow{19     int s,t,tot,now[maxn],son[maxm],pre[maxm],val[maxm];20     int dis[maxn],head,tail,list[maxn];21     bool bo[maxn];22     void init(){s=0,t=n+1,tot=1,memset(now,0,sizeof(now));}23     void put(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}24     void add(int a,int b,int c){put(a,b,c),put(b,a,0);}25     bool bfs(){26         memset(bo,0,sizeof(bo));27         head=0,tail=1,list[1]=s,dis[s]=0,bo[s]=1;28         while (head