4514: [Sdoi2016]数字配对

Description

有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。

若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，

那么这两个数字可以配对，并获得 ci×cj 的价值。

一个数字只能参与一次配对，可以不参与配对。

在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。

---

对于满足条件的\(a_i/a_j\)一定要满足\(a_i\)的质因子个数比\(a_j\)大一

所以可以对于每个数的质因子个数建二分图，只有异侧才有连边

至于总价值不小于0，在总价值<0的时候停止就行了

---

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define M 1000001
#define LL long long 
using namespace std;LL t,n,m,k,a[M],b[M],c[M],edge[M],nex[M],head[M],ver[M],cnt=1,h[M],d[M],cs[M],inq[M],cur[M],w[M],e[M],ed,zz,ans;
queue <LL> q;
void add(LL x,LL y,LL z,LL co)
{ver[++cnt]=y; nex[cnt]=head[x]; head[x]=cnt; edge[cnt]=z; cs[cnt]=co;ver[++cnt]=x; nex[cnt]=head[y]; head[y]=cnt; edge[cnt]=0; cs[cnt]=-co;
}bool spfa()
{memset(d,0,sizeof(d));memcpy(cur, head, sizeof(head));while(q.size()) q.pop();memset(h,-0x3f,sizeof(h));q.push(0); d[0]=1; h[0]=0; while(q.size()){LL x=q.front(); q.pop(); inq[x]=0;for(LL i=head[x];i;i=nex[i])if(edge[i] && h[ver[i]]<h[x]+cs[i]){h[ver[i]]=h[x]+cs[i]; d[ver[i]]=d[x]+1; if(!inq[ver[i]]) q.push(ver[i]);inq[ver[i]]=1;}}if(d[t]) return 1;return 0;
}LL dinic(LL x,LL flow)
{if(!flow || x==t) return flow;LL re=flow, k;for(LL & i=cur[x];i && re;i=nex[i])if(edge[i] && h[ver[i]]==h[x]+cs[i] && d[ver[i]]==d[x]+1){k=dinic(ver[i],min(re, edge[i]));re-=k; edge[i]-=k; edge[i^1]+=k;}return flow-re;
}LL fj(LL x)
{if(x==1) return 0;LL k=sqrt(x),ans=0; k+=1;for(LL i=2;i<=k;i++) if(x%i==0) while(x%i==0) x/=i,ans+=1;if(x!=1) ans+=1;return ans;
}int main()
{scanf("%lld",&n); t=n+1;for(LL i=1;i<=n;i++) scanf("%lld",&a[i]);for(LL i=1;i<=n;i++) scanf("%lld",&b[i]);for(LL i=1;i<=n;i++) scanf("%lld",&c[i]);for(LL i=1;i<=n;i++) w[i]=fj(a[i]);for(LL i=1;i<=n;i++) if(w[i]%2)for(LL j=1;j<=n;j++) if(w[j]%2==0 && ((a[i]%a[j]==0 && w[i]==w[j]+1)||(a[j]%a[i]==0 && w[j]==w[i]+1)))add(i,j,0x3f3f3f3f,c[i]*c[j]);for(LL i=1;i<=n;i++) if(w[i]%2) add(0,i,b[i],0);else add(i,t,b[i],0);while(spfa()){bool bll=1;while(k=dinic(0,0x3f3f3f3f)) {if(ed+h[t]*k<0) {ans+=ed/(-h[t]); bll=0; break;}ed+=h[t]*k, ans+=k;}if(!bll) break;}printf("%lld",ans);
}