3275: Number

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1259  Solved: 534

[][][]

Description

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

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

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

2:gcd(a,b)=1

Input

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

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

Output

最大的和

Sample Input

5

3 4 5 6 7

Sample Output

22

 

总感觉以前做过2333

    因为奇数和奇数的平方和不可能是完全平方数(考虑用(2*n+1)表示奇数，展开之后发现平方和是个偶数却%4余2，所以肯定不是完全平方数)，而偶数和偶数的

gcd至少是2。

    所以可以发现不满足条件的一定是一奇一偶，然后这题就是个二分图最大独立集了233

 

#include
      
       #define ll long long#define maxn 3005#define pb push_backusing namespace std;const int inf=1<<30;vector
       
         g[maxn];struct lines{    int to,flow,cap;}l[maxn*1000];int S,T,t=-1,d[maxn],cur[maxn];bool v[maxn];  inline void add(int from,int to,int cap){    l[++t]=(lines){to,0,cap},g[from].pb(t);    l[++t]=(lines){from,0,0},g[to].pb(t);}  inline bool BFS(){    memset(v,0,sizeof(v));    queue
        
          q;    q.push(S),v[S]=1,d[S]=0;    int x; lines e;           while(!q.empty()){        x=q.front(),q.pop();        for(int i=g[x].size()-1;i>=0;i--){            e=l[g[x][i]];            if(e.flow