sxczf's Blog

第一行一个正整数N。

第二行共包括N个正整数，第 个正整数表示Ai。

第三行共包括N个正整数，第 个正整数表示Bi。

共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
#define maxlongint 2147483647
#define maxn 10005
#define maxm 10000005
using namespace std;
int a[maxn],b[maxn],c,d,e,g,h,i,j,k,l,m,n,Ans,Dis[maxn],Flag,S,T,Tot;
int Way[maxm],Last[maxn],Next[maxm],Cost[maxm];
int min(int a,int b){if (a<b)return a;return b;}
void Spfa(){
     int Now,Head,Tail,Dl[maxn],Flag[maxn];
     memset(Dis,0x7f,sizeof(Dis));
     memset(Flag,0,sizeof(Flag));
     Head=1;Tail=1;Dis[S]=0;Dl[1]=S;
     for (;Head<=Tail;++Head){
         Now=Dl[Head];
         Flag[Now]=1;
         for (int i=Last[Now];i;i=Next[i])
         if ((Cost[i])&&(Dis[Way[i]]>Dis[Now]+1)){
                    Dis[Way[i]]=Dis[Now]+1;
                    if (!Flag[Way[i]]){Dl[++Tail]=Way[i];Flag[Way[i]]=1;}
             }
         }
     }
int dfs(int x,int Flow){
    if (Flow==0)return 0;
    if (x==T){Flag=1;return Flow;}
    int Sum=0,Tmp=0;
    for (int i=Last[x];i;i=Next[i])
    if (Dis[Way[i]]==Dis[x]+1){
                                  Tmp=dfs(Way[i],min(Flow-Sum,Cost[i]));
                                  Sum+=Tmp;
                                  Cost[i]-=Tmp;
                                  Cost[i^1]+=Tmp;
                                  if (Sum>=Flow)return Flow;
                                  }
       return Sum;
}
inline void make(int a,int b,int c){
	Way[++Tot]=b;
	Next[Tot]=Last[a];
	Last[a]=Tot;
	Cost[Tot]=c;
	Way[++Tot]=a;
	Next[Tot]=Last[b];
	Last[b]=Tot;
	Cost[Tot]=0;
}
int gcd(int a,int b){if (!b)return a;return gcd(b,a%b);}
int main(){
	Tot=1;
	scanf("%d",&n);S=n+1;T=n+2;
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++){scanf("%d",&b[i]);m=m+b[i];}
	for(i=1;i<=n;i++)if (a[i]&1){
		make(S,i,b[i]);
	}else{
		make(i,T,b[i]);
	}
	for(i=1;i<=n;i++)if (a[i]&1)
	for(j=1;j<=n;j++)if (!(a[j]&1))
	if (gcd(a[i],a[j])==1){
		long long H=1ll*a[i]*a[i]+1ll*a[j]*a[j];
		double G=sqrt(H);
		long long HH=(long long)(G);
		if ((1ll*HH*HH==H))make(i,j,maxlongint);
	}
    Flag=1;
    for (;Flag;){
        Spfa();
        Flag=0;
        Ans+=dfs(S,maxlongint);
        }
    printf("%d\n",m-Ans);
    for(;;);
    return 0;
}