Eva

Limit: 10 Sec  Memory Limit: 128 MB
Description

有N个正整数，需要从中选出一些数，使这些数的和最大。
若两个数a,b同时满足以下条件，则a,b不能同时被选
1:存在正整数C，使a*a+b*b=c*c
2:gcd(a,b)=1

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

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

最大的和

5
3  4 5 6 7

22

/**************************************************************

    Problem: 3275

    User: ictsing

    Language: C++

    Result: Accepted

    Time:1560 ms

    Memory:7256 kb

****************************************************************/

 

//BZOJ3275 Number

#include <iostream>

#include <cstdio>

#include <queue>

#include <cmath>

using namespace std;

const int inf = 0x7fffffff;

int ecnt=1;

int ans=0,tot=0;

const int mt =6000+5;

const int mm =250000+5;

int to[mm<<1],nxt[mm<<1],adj[mt],cap[mm<<1];

int lev[mt],cur[mt];

int a[mt];

int s,t=6000+3;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void adde(int u,int v,int w)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],cap[ecnt]=w,adj[u]=ecnt;

    ecnt++,to[ecnt]=u,nxt[ecnt]=adj[v],cap[ecnt]=0,adj[v]=ecnt;

}

int gcd(int a,int b)

{

    if(b==0) return a;

    return gcd(b,a%b);

}

bool check(int a,int b)

{

    int s=a*a+b*b,q=int(sqrt(s));

    if(q*q!=s) return 0;

    if(gcd(a,b)!=1) return 0;

    return 1;

}

queue<int>q;

bool bfs()

{

    while(!q.empty()) q.pop();

    for(int i=s;i<=t;i++) lev[i]=-1,cur[i]=adj[i];

    q.push(s),lev[s]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=adj[u];i;i=nxt[i])

        {

            int v=to[i];

            if(lev[v]==-1&&cap[i])

            {

                lev[v]=lev[u]+1;

                q.push(v);

                if(v==t) return true;

            }

        }

    }

    return false;

}

int dfs(int u,int flow)

{

    if(u==t||flow==0) return flow;

    int delta,res=0;

    for(int &i=cur[u];i;i=nxt[i])

    {

        int v=to[i];

        if(lev[v]==lev[u]+1&&cap[i])

        {

            delta=dfs(v,min(cap[i],flow-res));

            cap[i]-=delta,cap[i^1]+=delta,res+=delta;

            if(res==flow) return flow;

        }

    }

    if(res<flow) lev[u]=-1;

    return res;

}

void mincut()

{

    while(bfs())

        ans+=dfs(s,inf);

}

int main()

{

    int n=read();

    for(int i=1;i<=n;i++)

    {

        a[i]=read();

        adde(s,i,a[i]);

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

        tot+=a[i];

    }

    for(int i=1;i<=n;i++)

        for(int j=i+1;j<=n;j++)

            if(check(a[i],a[j]))

                adde(i,j+n,inf),adde(j,i+n,inf);

    mincut();

    printf("%d\n",tot-ans/2);

    return 0;

}