题目链接
一开始思路是错的，直接把可以连边的A_i A_j连在一起了，然后就会产生某个数的汇聚流量<使用流量。我们按每个数的质因子个数建图，奇数个的建在左图，反之建立在右图。然后一个二分图产生了。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<queue>
#define N 300000
using namespace std;
const long long INF=-0x8f8f8f8f8f8f8f8fll;
int n,S,T;
long long ans;
int pri[31634],tot;
bool e[31634],pc[N];
int a[N],d[N];
long long b[N],c[N];
int fir[N],nes[N],v[N],top=1,bak[N],road[N];
long long q[N],w[N],f[N];
bool prime(int x)
{
    for(int i=1;i<=tot;i++)
        if(x==pri[i]) return true;
        else if(x%pri[i]==0) return false;

    return true;
}
void edge(int x,int y,long long z,long long p)
{
    top++;
    bak[top]=x; v[top]=y;
    q[top]=z; w[top]=p;
    nes[top]=fir[x];fir[x]=top;
    return;
}
#define edge(x,y,z,p) edge(x,y,z,p),edge(y,x,0,-p)
bool spfa()
{
    queue<int> V;
    memset(f,0x8f,sizeof(f));
    V.push(S); f[S]=0; pc[S]=true;
    while(!V.empty())
    {
        int c=V.front();
        for(int t=fir[c];t;t=nes[t])
        {
            if(!q[t] || f[v[t]]>=f[c]+w[t]) continue;
            f[v[t]]=f[c]+w[t]; road[v[t]]=t;
            if(pc[v[t]]) continue;
            V.push(v[t]); pc[v[t]]=true;
        }
        V.pop(); pc[c]=false;
    }
    return f[T]!=-INF;
}
void fly()
{
    long long cs=0;
    while(spfa())
    {
        long long c=INF;
        for(int t=T;t!=S;t=bak[road[t]]) c=min(c,q[road[t]]);
        if(f[T]*c+cs>=0) {ans+=c; cs+=f[T]*c;}
        else {ans+=cs/(-f[T]); break;}
        for(int t=T;t!=S;t=bak[road[t]])
        {
            q[road[t]]-=c;
            q[road[t]^1]+=c;
        }
    }
    return;
}
int main()
{
    scanf("%d",&n);
    S=n+1; T=S+1;
    for(int i=2;i<=31633;i++) if(!e[i])
        for(int j=i+i;j<=31633;j+=i) e[j]=true;
    for(int i=2;i<=31633;i++) if(!e[i]) pri[++tot]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        int t=a[i],sum=0,radical=sqrt(a[i]);
        for(int j=1;j<=tot;j++)
        {
            while(t%pri[j]==0) sum++,t/=pri[j];
            if(t==1) break;
            if(pri[j]>radical) break;
        }
        if(t!=1) sum++;
        d[i]=sum%2;
    }
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<=n;i++)
    {
        if(d[i])  edge(S,i,b[i],0);
        else     {edge(i,T,b[i],0); continue;}
        for(int j=1;j<=n;j++)
        {
            if(d[j]) continue;
            int x=a[i],y=a[j];
            if(x<y) swap(x,y);
            if(x%y!=0) continue;
            if(prime(x/y)) edge(i,j,INF,c[i]*c[j]);
        }
    }
    fly();
    printf("%lld",ans);
    return 0;
}