思路：
很受伤现在，，测了那么多次不过的原因就是因为INF不够大；
解法有两种：
解法1：
把n个点按照质因数个数为奇或偶分为两个点集（很容易就可以想到）；
然后，按照题目连边跑最大费用流；
当累计的能量马上就要小于0时，退出循环，输出答案；
解法2：
把n个点拆成2*n个点，也是两个集合；
如果ai[i]到ai[j]可以连边，则i连j+n，同时j连i+n；
当累计的能量马上就要小于0时，退出循环，输出答案/2；
来，上代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define ll long long
#define INF 0x7ffffffffff ll n,prime[],num_prime=,ai[],bi[],ci[];
ll s,t,head[],E[],V[],W[],F[];
ll cnt=,pre[],que[],dis[]; bool if_prime[],d1iv[],if_[]; inline void in(ll &now)
{
ll if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} void euler(ll limit)
{
for(ll i=;i<=limit;i++)
{
if(!if_prime[i]) prime[++num_prime]=i;
for(ll j=;prime[j]*i<=limit&&j<=num_prime;j++)
{
if_prime[i*prime[j]]=true;
if(i%prime[j]==) break;
}
}
} inline bool cut(ll op)
{
ll res=,now=;
while(op!=&&now<)
{
now++;
while(!(op%prime[now])) op/=prime[now],res++;
}
return res&;
} inline void edge_add(ll u,ll v,ll w,ll f)
{
E[++cnt]=head[u],head[u]=cnt,W[cnt]=w,F[cnt]=f,V[cnt]=v;
E[++cnt]=head[v],head[v]=cnt,W[cnt]=-w,F[cnt]=,V[cnt]=u;
} inline bool spfa()
{
for(ll i=s;i<=t;i++) dis[i]=-INF,if_[i]=false,pre[i]=-;
ll h=,tail=;que[]=s,if_[s]=true,dis[s]=;
while(h<tail)
{
ll now=que[h++];if_[now]=false;
for(ll i=head[now];i;i=E[i])
{
if(F[i]>&&dis[V[i]]<dis[now]+W[i])
{
pre[V[i]]=i;
dis[V[i]]=dis[now]+W[i];
if(!if_[V[i]])
{
if_[V[i]]=true;
que[tail++]=V[i];
}
}
}
}
return dis[t]!=-INF;
} int main()
{
in(n);euler(),t=n+;
for(ll i=;i<=n;i++) in(ai[i]);
for(ll i=;i<=n;i++) in(bi[i]);
for(ll i=;i<=n;i++) in(ci[i]);
for(ll i=;i<=n;i++)
{
if(cut(ai[i]))
{
d1iv[i]=true;
edge_add(i,t,,bi[i]);
}
else edge_add(s,i,,bi[i]);
}
for(ll i=;i<=n;i++)
{
if(!d1iv[i])
{
for(ll j=;j<=n;j++)
{
if(d1iv[j])
{
ll a=max(ai[i],ai[j]),b=min(ai[i],ai[j]);
if(a==b||a%b) continue;
if(!if_prime[a/b]) edge_add(i,j,ci[i]*ci[j],INF);
}
}
}
}
ll ans=,cii=;
while(spfa())
{
ll now=t,pos=INF;
while(pre[now]!=-)
{
pos=min(pos,F[pre[now]]);
now=V[pre[now]^];
}
now=t;
while(pre[now]!=-)
{
F[pre[now]]-=pos;
F[pre[now]^]+=pos;
now=V[pre[now]^];
}
if(cii+dis[t]*pos<)
{
ans+=cii/(-dis[t]);
break;
}
ans+=pos,cii+=dis[t]*pos;
}
cout<<ans;
return ;
}
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 205
#define maxm 1000005
#define ll long long
#define INF 0x7ffffffffff ll que[maxm],E[maxm],V[maxm],F[maxm],W[maxm],cnt=,bi[maxn];
ll n,head[maxn<<],s,t,dis[maxn<<],pre[maxn<<],ai[maxn],ci[maxn]; bool if_[maxn<<]; inline void in(ll &now)
{
ll if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} inline void edge_add(ll u,ll v,ll w,ll f)
{
E[++cnt]=head[u],V[cnt]=v,W[cnt]=w,F[cnt]=f,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,W[cnt]=-w,F[cnt]=,head[v]=cnt;
} inline bool judge(ll op)
{
ll lit=sqrt(op);
for(ll i=;i<=lit;i++) if(!(op%i)) return false;
return true;
} inline bool spfa()
{
for(ll i=s;i<=t;i++) dis[i]=-INF,pre[i]=-,if_[i]=false;
ll h=,tail=;dis[s]=,que[]=s,if_[s]=true;
while(h<tail)
{
ll now=que[h++];if_[now]=false;
for(ll i=head[now];i;i=E[i])
{
if(F[i]>&&dis[V[i]]<dis[now]+W[i])
{
pre[V[i]]=i,dis[V[i]]=dis[now]+W[i];
if(!if_[V[i]]) if_[V[i]]=true,que[tail++]=V[i];
}
}
}
return dis[t]!=-INF;
} int main()
{
freopen("menci_pair.in","r",stdin);
freopen("menci_pair.out","w",stdout);
in(n),t=n<<|;
for(ll i=;i<=n;i++) in(ai[i]);
for(ll i=;i<=n;i++)
{
in(bi[i]);
edge_add(s,i,,bi[i]);
edge_add(i+n,t,,bi[i]);
}
for(ll i=;i<=n;i++) in(ci[i]);
for(ll i=;i<=n;i++)
{
for(ll j=;j<=n;j++)
{
if(ai[i]<=ai[j]||ai[i]%ai[j]) continue;
if(judge(ai[i]/ai[j]))
{
edge_add(i,j+n,ci[i]*ci[j],INF);
edge_add(j,i+n,ci[i]*ci[j],INF);
}
}
}
ll ans=,cii=;
while(spfa())
{
ll now=t,pos=INF;
while(pre[now]!=-)
{
pos=min(pos,F[pre[now]]);
now=V[pre[now]^];
}
now=t;
while(pre[now]!=-)
{
F[pre[now]]-=pos;
F[pre[now]^]+=pos;
now=V[pre[now]^];
}
if(cii+dis[t]*pos<)
{
ans+=cii/abs(dis[t]);
break;
}
ans+=pos,cii+=dis[t]*pos;
}
cout<<ans/;
return ;
}