题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3158
( a[i] ) 是奇数则满足条件1，是偶数则显然满足条件2；
因为如果把两个奇数的 ( a[i] ) 写成 ( 2*n+1 ) 和 ( 2*m+1 )，那么：
( a[i]^{2} + a[j]^{2} = (2*n+1)^{2} + (2*m+1)^{2} = 4*(n^{2}+n+m^{2}+m) + 2 )
这是个偶数，所以如果它是完全平方数，那么一定是一个偶数的平方，那么那个 ( +2 ) 就没有办法了，所以它一定不是一个完全平方数；
于是可以把点分成两部分；
然后用最小割的思路，不能一起选就连边，两部分内部的点显然是不互相连边的；
然后原点、汇点分别和两个部分有 ( b[i] ) 的边，跑最小割即可。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; typedef long long ll; int const xn=1005,xm=520005,inf=1e9; int n,hd[xn],ct=1,nxt[xm],to[xm],c[xm],dis[xn],cur[xn],S,T,a[xn],b[xn]; queue<int>q; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } void ade(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;} void add(int x,int y,int z){ade(x,y,z); ade(y,x,0);} bool ck(int a,int b) { ll x=(ll)a*a+(ll)b*b; ll t=(ll)sqrt(x); return t*t==x; } int gcd(int a,int b){return b?gcd(b,a%b):a;}; bool bfs() { for(int i=S;i<=T;i++)dis[i]=0; dis[S]=1; q.push(S); while(q.size()) { int x=q.front(); q.pop(); for(int i=hd[x],u;i;i=nxt[i]) if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+1,q.push(u); } return dis[T]; } int dfs(int x,int fl) { if(x==T)return fl; int ret=0; for(int &i=cur[x],u;i;i=nxt[i]) { if(dis[u=to[i]]!=dis[x]+1||!c[i])continue; int tmp=dfs(u,min(fl-ret,c[i])); if(!tmp)dis[u]=0; c[i]-=tmp; c[i^1]+=tmp; ret+=tmp; if(ret==fl)break; } return ret; } int main() { n=rd(); S=0; T=n+1; int ans=0; for(int i=1;i<=n;i++)a[i]=rd(); for(int i=1;i<=n;i++)b[i]=rd(),ans+=b[i]; for(int i=1;i<=n;i++) if(a[i]&1)add(S,i,b[i]); else add(i,T,b[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(ck(a[i],a[j])&&gcd(a[i],a[j])==1) { if(a[i]&1)add(i,j,inf); else add(j,i,inf); } while(bfs()) { memcpy(cur,hd,sizeof hd); ans-=dfs(S,inf); } printf("%d ",ans); return 0; }