显示代码纯文本
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int inf=0x7fffffff;
const int N=210;
const int S=201;
const int T=202;
struct node{int qi,zhong,flow,next;LL val;}s[(N*N)<<1];
inline int min(int a,int b){return a<b?a:b;}
int adj[N],e=1,flow;LL ans;
void add(int qi,int zhong,LL val,int flow)
{
s[++e].qi=qi;s[e].zhong=zhong;
s[e].flow=flow;s[e].val=val;
s[e].next=adj[qi],adj[qi]=e;
}
int ss[N],t[N],cnts,cntt;
int n,a[N],b[N],ci[N];//a数值,b个数,c权值
LL c[N];
int vis[N],p[N];queue<int>q;
LL dis[N];
inline void divide(int x)
{
int cnt=0,tmp=a[x];
//printf("tmp=%d ",tmp);
for(int i=2;i*i<=tmp;i++)
if(!(tmp%i))
while(!(tmp%i))cnt++,tmp/=i;
if(tmp>1)cnt++;
//printf("cnt=%d",cnt);
ci[x]=cnt;
if(cnt&1)ss[++cnts]=x;
else t[++cntt]=x;
}
inline bool spfa()
{
memset(dis,0xaf,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(p,0,sizeof(p));LL tmp=dis[1];
dis[S]=0;vis[S]=1;p[S]=0;q.push(S);
while(!q.empty())
{
int rt=q.front();q.pop();vis[rt]=0;
for(int i=adj[rt];i;i=s[i].next)
{
int u=s[i].zhong;
if(s[i].flow&&dis[u]<dis[rt]+s[i].val)
{
dis[u]=dis[rt]+s[i].val;p[u]=i;
if(!vis[u])q.push(u),vis[u]=1;
}
}
}
//printf("dis=%d",dis[T]);
if(dis[T]==tmp)return 0;
int u=T,f=inf;
while(u!=S)
{
f=min(f,s[p[u]].flow);
u=s[p[u]].qi;
}u=T;//printf(" %d\n",f);
if(ans+dis[T]*f<0){flow+=-ans/dis[T];return 0;}
flow+=f;ans+=f*dis[T];
while(u!=S)
{
s[p[u]].flow-=f;
s[p[u]^1].flow+=f;
u=s[p[u]].qi;
}
return 1;
}
int main()
{
//freopen("Lex.txt","r",stdin);
freopen("menci_pair.in","r",stdin);
freopen("menci_pair.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);divide(i);}
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
for(int i=1;i<=cnts;i++)add(S,ss[i],0,b[ss[i]]),add(ss[i],S,0,0);
for(int i=1;i<=cntt;i++)add(t[i],T,0,b[t[i]]),add(T,t[i],0,0);
//for(int i=1;i<=cnts;i++)printf("ss%d ",ss[i]);printf("\n");
//for(int i=1;i<=cntt;i++)printf("t%d ",t[i]);printf("\n");
for(int i=1;i<=cnts;i++)
for(int j=1;j<=cntt;j++)
if(ci[ss[i]]==ci[t[j]]+1)
{
double tmp=(a[ss[i]]*1.0)/a[t[j]];int tm=tmp;
if(tmp-tm!=0)continue;
//printf("%d %d %d\n",ss[i],t[j],c[ss[i]]*c[t[j]]);
add(ss[i],t[j],c[ss[i]]*c[t[j]],inf),add(t[j],ss[i],-c[ss[i]]*c[t[j]],0);
}
else if(ci[ss[i]]==ci[t[j]]-1)
{
double tmp=(a[t[j]]*1.0)/a[ss[i]];int tm=tmp;
if(tmp-tm!=0)continue;
//printf("%d %d %d\n",ss[i],t[j],c[ss[i]]*c[t[j]]);
add(ss[i],t[j],c[ss[i]]*c[t[j]],inf),add(t[j],ss[i],-c[ss[i]]*c[t[j]],0);
}
while(spfa());
printf("%d",flow);
}
LadyLex