显示代码纯文本
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline int min(int x,int y){return x<y?x:y;}
const int N=210,M=100010,maxl=1e9;
typedef long long ll;
int n,a[N],b[N],c[N],d[N],x[N],y[N],s,t1,t;
int P[N][N],A[N][N],num[N],sum[N];//分解质因数
bool f[N][N],tag[N];
void fenjie(int p){
int x=a[p];
for (int i=2;i<=sqrt(x);i++)
if (!(x%i)){
P[p][++num[p]]=i;
while (!(x%i)) x/=i,A[p][num[p]]++;
}
if (x!=1) num[p]++,P[p][num[p]]=x,A[p][num[p]]=1;
for (int i=1;i<=num[p];i++) sum[p]+=A[p][i];
tag[p]=sum[p]&1;
}
struct edge{
int f,t,g,o;ll l;
edge(int F=0,int T=0,int G=0,int O=0,ll L=0){
f=F;t=T;g=G;o=O;l=L;
}
}w[M];
int head[N],tail[N],next[M],cnt;
inline void add(int f,int t,int g,ll l){
cnt++;w[cnt]=edge(f,t,g,cnt+1,l);
if (!head[f]) head[f]=tail[f]=cnt;
else tail[f]=next[tail[f]]=cnt;
cnt++;w[cnt]=edge(t,f,0,cnt-1,-l);
if (!head[t]) head[t]=tail[t]=cnt;
else tail[t]=next[tail[t]]=cnt;
}
int flow[N],from[N];ll dis[N];bool vis[N];
ll cost,Flow;
inline void Init(){//初始化图
for (int i=1;i<=cnt;i++) next[i]=0;
for (int i=s;i<=t;i++) head[i]=tail[i]=0;
cost=Flow=cnt=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (tag[i]&&f[i][j]) add(i,j,maxl,-(ll)c[i]*c[j]);
for (int i=1;i<=n;i++)
if (tag[i]) add(s,i,b[i],0);
else add(i,t1,b[i],0);
}
inline bool spfa(){//最小费用最大流
queue<int> Q;
for (int i=s;i<=t;i++) dis[i]=1e16,vis[i]=0;
dis[s]=0;flow[s]=maxl;Q.push(s);vis[s]=1;
while (!Q.empty()){
int v=Q.front();Q.pop();
vis[v]=0;
for (int i=head[v];i;i=next[i])
if (w[i].g&&dis[w[i].t]>dis[v]+w[i].l){
dis[w[i].t]=dis[v]+w[i].l;
flow[w[i].t]=min(flow[v],w[i].g);
from[w[i].t]=i;
if (!vis[w[i].t]) Q.push(w[i].t),vis[w[i].t]=1;
}
}
if (dis[t]!=1e16){
int df=flow[t];
Flow+=df;cost+=dis[t]*df;
for (int i=from[t];i;i=from[w[i].f])
w[i].g-=df,w[w[i].o].g+=df;
return 1;
}
return 0;
}
int erfen(int l,int r){
if (l==r) return l;
int mid=(l+r)/2;
Init();add(t1,t,mid+1,0);
while (spfa());
if (Flow==mid+1&&cost<=0) return erfen(mid+1,r);
return erfen(l,mid);
}
int main()
{
freopen("menci_pair.in","r",stdin);
freopen("menci_pair.out","w",stdout);
scanf("%d",&n);
s=0;t1=n+1;t=n+2;
int Sum=0;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]),Sum+=b[i];
for (int i=1;i<=n;i++) scanf("%d",&c[i]);
for (int i=1;i<=n;i++) fenjie(i);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (!(a[i]%a[j])){
for (int p=1,x=a[i]/a[j];p<=num[i];p++)
if (x==P[i][p]) f[i][j]=f[j][i]=1;
}
printf("%d\n",erfen(0,Sum/2));
return 0;
}
FoolMike