其实稍加思考发现$(i,j)$能连边,如果以它们的质因子个数为准的话,这其实是个二分图。
那么题目就变成了最大费用流,由于spfa的值会越来越小,只要在费用小于$0$时候停止就好了。
可以很形象地理解成交易市场,$i$带着$B_i$的筹码,从起点来,$j$带着$B_j$的筹码,从终点来,它们能交易$\min\{B_i,B_j\}$。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,Max=1e9,M=1010;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
bool v[N];
int calc(int x)
{
int ret=0;
for(int i=2;1ll*i*i<=x;i++)
while(x%i==0)x/=i,++ret;
if(x!=1)++ret;return ret;
}
struct edge{int y,c,next;ll d;}a[N<<1];int last[M],len;
void ins(int x,int y,int c,ll d)
{
a[++len]=(edge){y,c,last[x],d};last[x]=len;
a[++len]=(edge){x,0,last[y],-d};last[y]=len;
}
int A[M],B[M],C[M],n,st,ed,w[N];
void prepare()
{
len=1;st=n+1,ed=st+1;
for(int i=1;i<=n;i++)w[i]=calc(A[i]);
for(int i=1;i<=n;i++)
if(w[i]&1)
{
ins(st,i,B[i],0);
for(int j=1;j<=n;j++)if(i!=j)
{
if(A[j]%A[i]==0&&w[j]==w[i]+1)ins(i,j,min(B[i],B[j]),1ll*C[i]*C[j]);
else if(A[i]%A[j]==0&&w[i]==w[j]+1)ins(i,j,min(B[i],B[j]),1ll*C[i]*C[j]);
}
}
else ins(i,ed,B[i],0);
}
int f[N],q[N],prv[N];ll d[N];
bool spfa()
{
memset(v,0,sizeof(v));
memset(f,0,sizeof(f));f[st]=0x3f3f3f3f;memset(d,0xcf,sizeof(d));int l=1,r=2;q[1]=st;v[st]=1;d[st]=0;
while(l!=r)
{
int x=q[l++];v[x]=0;if(l==n+3)l=1;
for(int k=last[x],y;k;k=a[k].next)
{
y=a[k].y;
if(d[y]<d[x]+a[k].d&&a[k].c)
{
d[y]=d[x]+a[k].d;
f[y]=min(f[x],a[k].c);
prv[y]=k;
if(!v[y]){v[y]=1;q[r++]=y;if(r==n+3)r=1;}
}
}
}
return f[ed];
}
ll ans=0,s=0;
void del()
{
int y=ed,k=prv[y],ret=0;
while(k)
{
a[k].c-=f[ed];
a[k^1].c+=f[ed];
k=prv[a[k^1].y];
}
s+=d[ed]*f[ed];
if(s<0)ret=(-s)/(-d[ed])+(!((-s)%(-d[ed])==0));
ans+=f[ed]-ret;
}
int main()
{
qr(n);
for(int i=1;i<=n;i++)qr(A[i]);
for(int i=1;i<=n;i++)qr(B[i]);
for(int i=1;i<=n;i++)qr(C[i]);
prepare();
while(spfa()&&s>=0)
del();
qw(ans);puts("");
return 0;
}
最后一次更新于2020-03-21
0 条评论