题目分析:
两个点同时选会有inf的代价,需要满足二分图性质
- 两个偶数的gcd不为1
- 两个奇数的平方和不可能是完全平方数,因为奇数可以写成2k+1, 平方模4余1,两个平方的和模4余2且为偶数,而偶数的平方模4余0,所以不可能是平方数
所以两个不能同时选的数一定是一奇一偶,二分图,加上权值跑最小割即可
#include
#include
#include
#include
#include
#include
#define LL long long
#define maxn 3005
#define maxm 1000005
using namespace std;
char cb[1<<15],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
inline void read(int &a){
char c;bool f=0;
while(!isdigit(c=getc())) if(c=='-') f=1;
for(a=c-'0';isdigit(c=getc());a=a*10+c-'0');
if(f) a=-a;
}
const int inf = 0x3f3f3f3f;
int n,m,S,T;
int fir[maxn],cur[maxn],dis[maxn],nxt[maxm],to[maxm],tot=1,cap[maxm],sum;
inline void line(int x,int y,int z,int rz=0){
nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,cap[tot]=z;
nxt[++tot]=fir[y],fir[y]=tot,to[tot]=x,cap[tot]=rz;
}
queue<int>q;
bool bfs()
{
memset(dis,0,(T+1)<<2);
dis[T]=1,q.push(T);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=fir[u];i;i=nxt[i]) if(cap[i^1]&&!dis[to[i]]){
dis[to[i]]=dis[u]+1;
q.push(to[i]);
}
}
return dis[S];
}
int dfs(int u,int lim)
{
if(u==T) return lim;
int need=lim,delta;
for(int &i=cur[u];i;i=nxt[i]) if(cap[i]&&dis[u]==dis[to[i]]+1){
delta=dfs(to[i],min(cap[i],need));
cap[i]-=delta,cap[i^1]+=delta;
if(!(need-=delta)) break;
}
return lim-need;
}
int Dinic(){
int flow=0;
while(bfs()) memcpy(cur,fir,(T+1)<<2),flow+=dfs(S,inf);
return flow;
}
int a[maxn],in[maxn];
inline bool check(int x){int y=int(sqrt(x));return y*y==x;}
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main()
{
read(n);S=0,T=n+1;
for(int i=1;i<=n;i++){
read(a[i]),sum+=a[i];
if(a[i]&1) line(S,i,a[i]);
else line(i,T,a[i]);
for(int j=i-1;j>=1;j--) if(check(a[i]*a[i]+a[j]*a[j])&&gcd(a[i],a[j])==1){
if(a[i]&1) line(i,j,inf);
else line(j,i,inf);
}
}
printf("%d",sum-Dinic());
}