Lvat_s Blog

用二分图建图再跑最大费用最大流就可以了

考场上建图写炸了。。。sad

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
 
const long long INF=1000000000000000ll;
 
int n,en,S,T,h[10005],flag[10005],Back[10005],Tag,tab[100005],cnt,X[10005],Y[10005],xs=0,ys=0;
long long A[2005],B[2005],C[2005],D[10005],Cost=0;
queue<int> Q;
 
struct Edge{
int b,back,next;
long long f,c;
}e[2000005];
 
void AddEdge(int sa,int sb,long long sc,long long sd){
e[++en].b=sb;
e[en].back=en+1;
e[en].f=sc;
e[en].c=sd;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].back=en-1;
e[en].f=0;
e[en].c=-sd;
e[en].next=h[sa];
h[sa]=en;
}
 
bool SPFA(){
memset(D,-80,sizeof(D));
memset(flag,0,sizeof(flag));
memset(Back,0,sizeof(Back));
D[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(D[u]+e[i].c>D[v] && e[i].f){
            D[v]=D[u]+e[i].c;
            Back[v]=i;
            if(!flag[v]){
                flag[v]=1;
                Q.push(v);
            }
        }
    }
}
return D[T]>-INF;
}
 
long long Flow(){
long long ans=INF,Co=0;
int Tx=Back[T];
while(Tx){
    ans=min(ans,e[Tx].f);
    Co+=e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
while(Cost+ans*Co<0)ans--;if(ans<=0){Tag=1;return 0;}
Tx=Back[T];
while(Tx){
    e[Tx].f-=ans;
    e[e[Tx].back].f+=ans;
    Cost+=ans*e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
return ans;
}
 
long long MaxCost(){
long long ans=0;
while(SPFA()){
    ans+=Flow();
    if(Tag)break;
}
return ans;
}
 
bool Test(int x){
if(x==1 || x==0)return 0;
for(int i=2;i*i<=x;i++){
    if(x%i==0)return 0;
}
return 1;
}
 
bool Testx(long long x){
if(x==1 || x==0)return 0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    if(x%tab[i]==0)return 0;
}
return 1;
}
 
void Prime(){
for(int i=2;i<=40000;i++){
    if(Test(i)){tab[++cnt]=i;}
}
}
 
int Count(long long x){
int px=0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    while(x%tab[i]==0){px++;x/=tab[i];}
}
if(x>1)px++;
return px;
}
 
int main(){
freopen("4514.in","r",stdin);
freopen("4514.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
for(int i=1;i<=n;i++)scanf("%lld",&B[i]);
for(int i=1;i<=n;i++)scanf("%lld",&C[i]);
Prime();
S=n+1;T=n+2;
for(int i=1;i<=n;i++){if(Count(A[i])&1)X[++xs]=i;else Y[++ys]=i;}
for(int i=1;i<=xs;i++)AddEdge(S,X[i],B[X[i]],0);
for(int i=1;i<=ys;i++)AddEdge(Y[i],T,B[Y[i]],0);
for(int i=1;i<=xs;i++){
    for(int j=1;j<=ys;j++){
        if(A[X[i]]%A[Y[j]]==0 && Testx(A[X[i]]/A[Y[j]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
        if(A[Y[j]]%A[X[i]]==0 && Testx(A[Y[j]]/A[X[i]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
    }
}
printf("%lld\n",MaxCost());
return 0;
}