题意:
有 $ n $ 种数字，第 $ i $ 种数字是 $ a_i $、有 $ b_i $ 个，权值是 $ c_i $。
若两个数字 $ a_i $、$ a_j $ 满足，$ a_i $ 是 $ a_j $ 的倍数，且 $ a_i / a_j $ 是一个质数，那么这两个数字可以配对，并获得 $ c_i cdot c_j $ 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 $ 0 $ 的前提下，求最多进行多少次配对。
$ n leq 200 $，$ a_i leq 10 ^ 9 $，$ b_i leq 10 ^ 5 $，$ left| c_i ight| leq 10 ^ 5 $。
题解:
阅读题目，观察到“配对”，“价值”，还有“只能参与一次配对”，容易联想到费用流。但是如果直接连边，似乎无法保证每个数字只能用 $b[i]$ 次。考虑这种配对问题，普通的费用流一般是怎么建边的，就是一些放左边，一些放右边，然后左右连边。但这道题似乎没有明显的划分依据。
先考虑把各种边连上，这样就连出来一个图（当它是无向图），想要将其划分为左右两边，相当于这张图可以 $0/1$ 染色，即这张图是二分图。那这张图是不是二分图？可以发现，对于图中任意一个环，也就是从一个点出发回到自己本身，每走一步必然是质因子次数总和变化 $1$，那么必然是走了偶数步。换句话说，这张图所有的环，都是偶环，那么就是二分图了。
然后问题就很简单了，二分图染色一下，$0$ 放左边，$1$ 放右边，连边完二分+费用流即可。
#include<cstdio> #include<vector> #include<cstring> #include<queue> #include<algorithm> #include<cstdlib> using namespace std; const long long INF=1e18; int n,aa[202],b[202],c[202],p[205],s=201,s2=202,t=203,ys[202]; long long d[205],a[205]; bool fl[205]; struct Edge{ int from,to; long long cap,flow,cost; Edge(int u,int v,long long c,long long f,long long w):from(u),to(v),cap(c),flow(f),cost(w){} }; vector<Edge>edges; vector<int>g[205],y[205]; void init(){ for (int i=1;i<=t;i++)g[i].clear(); edges.clear(); } void add(int from,int to,long long cap,long long cost){ edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); g[from].push_back(edges.size()-2); g[to].push_back(edges.size()-1); } bool spfa(int s,int t,long long& flow,long long& cost){ for (int i=1;i<=t;i++)d[i]=-INF; d[s]=0;fl[s]=1;a[s]=INF; queue<int>q;q.push(s);memset(fl,0,sizeof(fl)); while(!q.empty()) { int u=q.front();q.pop(); fl[u]=0; for (int i=0;i<g[u].size();i++) { Edge e=edges[g[u][i]]; if (e.cap>e.flow && d[u]+e.cost>d[e.to]) { d[e.to]=d[u]+e.cost; p[e.to]=g[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if (!fl[e.to]){q.push(e.to);fl[e.to]=1;} } } } if (d[t]==-INF)return false; flow+=a[t];cost+=d[t]*a[t]; for (int u=t;u!=s;u=edges[p[u]].from) { edges[p[u]].flow+=a[t];edges[p[u]^1].flow-=a[t]; } return true; } void dfs(int x){ for (int i=0;i<y[x].size();i++) if (ys[y[x][i]]==-1) { ys[y[x][i]]=(ys[x]^1);dfs(y[x][i]); } } bool pd(long long x){ init();add(s,s2,x,0); for (int i=1;i<=n;i++) if (ys[i]==0) { add(s2,i,b[i],0); for (int j=0;j<y[i].size();j++)add(i,y[i][j],INF,(long long)c[i]*c[y[i][j]]); } else add(i,t,b[i],0); long long flow=0,cost=0; while(spfa(s,t,flow,cost)); return (flow==x && cost>=0); } bool isprim(int x){ for (int i=2;i*i<=x;i++) if (x%i==0)return false; return true; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&aa[i]); for (int i=1;i<=n;i++)scanf("%d",&b[i]); for (int i=1;i<=n;i++)scanf("%d",&c[i]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (aa[i]%aa[j]==0 && isprim(aa[i]/aa[j]) || aa[j]%aa[i]==0 && isprim(aa[j]/aa[i])) { y[i].push_back(j);y[j].push_back(i); } memset(ys,-1,sizeof(ys)); for (int i=1;i<=n;i++)if (ys[i]==-1){ys[i]=0;dfs(i);} long long lef=0,righ=1000000000,mid; while(lef<righ) { mid=(lef+righ+1)/2; if (pd(mid))lef=mid;else righ=mid-1; } printf("%lld ",lef); return 0; }