用二分图建图再跑最大费用最大流就可以了
考场上建图写炸了。。。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;
}
这么一个式子(用画图画的请见谅……我不会LateX)
