题目大意

数据范围

$1\leqslant n\leqslant 1000,1\leqslant a_i,b_i\leqslant 10^6$

题解

首先要知道这样两个结论

1. 任意两个奇数满足第一个条件

设$a=2n+1,b=2m+1$，则$a^2+b^2=(2n+1)^2+(2m+1)^2=2(2n^2+2m^2+2n+2m+1)$，这一定不是完全平方数

2. 任意两个偶数满足第二个条件

很显然，任意两个偶数至少有公约数$2$

那么就可以奇偶二分图，汇点向第奇数个装置连一条边，第偶数个装置向汇点连一条边，边权都是对应装置的能量值

然后我们只要找到第奇数个装置与第偶数个装置间产生的关系来连几条边权无穷大的边就可以完成建图了

发现第奇数个装置和第偶数个装置如果不能存在于同一个集合中（两个条件都不满足）就可以连边，因为最小割只会把这两个点中的一个割去

最后把能量值总数减去最小割就是答案了

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,s,t,ans,et=1;
struct edge{int to,next,c;}e[1000500];
int a[1050],b[1050],d[1050],last[1050];
inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
inline void addedge(int u,int v,int c){
    e[++et]=(edge){v,last[u],c};last[u]=et;
    e[++et]=(edge){u,last[v],0};last[v]=et;
}
inline int judge(ll x,ll y){
    ll t=sqrt(x*x+y*y);
    if (x*x+y*y!=t*t) return 0;
    if (gcd(x,y)>1) return 0;
    return 1;
}

inline int bfs(){
    memset(d,-1,sizeof(d));
    queue <int> q;q.push(s);d[s]=0;
    while (!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h)
            if (d[e[i].to]==-1&&e[i].c){
                d[e[i].to]=d[h]+1;
                q.push(e[i].to);
    }        }
    return d[t]!=-1;
}

int dinic(int x,int flow){
    if (x==t) return flow;int a,used=0;
    goedge(i,x)
        if (e[i].c&&d[e[i].to]==d[x]+1){
            a=dinic(e[i].to,min(flow-used,e[i].c));
            e[i].c-=a,e[i^1].c+=a,used+=a;
            if (flow==used) return flow;
        }
    if (!used) d[x]=-1;
    return used;
}

int main(){
    n=read();s=0,t=n+1;
    For(i,1,n) a[i]=read();
    For(i,1,n) b[i]=read(),ans+=b[i];
    For(i,1,n) (a[i]&1)?addedge(s,i,b[i]):addedge(i,t,b[i]);
    For(i,1,n) For(j,1,n)
        if ((a[i]&1)&&((a[j]+1)&1)&&judge(a[i],a[j])) addedge(i,j,inf);
    while (bfs()) ans-=dinic(s,inf);
    printf("%d\n",ans);
}