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
#include
#include
#include
#include
#include
#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  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]]