题目描述
有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。
若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，
那么这两个数字可以配对，并获得 ci×cj 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
输入
第一行一个整数 n。
第二行 n 个整数 a1、a2、……、an。
第三行 n 个整数 b1、b2、……、bn。
第四行 n 个整数 c1、c2、……、cn。
输出
一行一个数，最多进行多少次配对
样例输入
3
2 4 8
2 200 7
-1 -2 1
2 4 8
2 200 7
-1 -2 1
样例输出
4
提示
n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5
有数量上限、有价值，显然费用流，因为题目要求费用不小于$0$，所以用最大费用最大流。将每个点拆成两个点$i$和$i'$，分别与源点和汇点连边，流量为$b[i]$、费用为$0$。枚举任意两个数判断是否能匹配。因为$i$与$j$能匹配，$j$就能与$i$匹配，所以将$i$与$j'$连边、$j$与$i'$连边，流量为$INF$、费用为$-c[i]*c[j]$(因为跑最大费用最大流，边权取反)。每次$SPFA$找到一条增广路，如果加上之后答案满足要求就继续增广，否则就停止。因为一对数的匹配算了两次，所以最后答案除$2$即可。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define INF 1000000000000000ll
#define inf 1000000000
using namespace std;
int head[1000];
int next[100000];
int to[100000];
ll v[100000];
int c[100000];
int f[1000];
int from[100000];
int tot=1;
int S,T;
ll ans;
int n;
int A[300];
int B[300];
int C[300];
queue<int>q;
int vis[1000];
ll d[1000];
int maxflow;
void add(int x,int y,ll z,int w)
{
next[++tot]=head[x];
head[x]=tot;
to[tot]=y;
v[tot]=z;
c[tot]=w;
from[tot]=x;
next[++tot]=head[y];
head[y]=tot;
to[tot]=x;
v[tot]=-z;
c[tot]=0;
from[tot]=y;
}
bool result()
{
int now=T;
int flow=inf;
while(now!=S)
{
flow=min(flow,c[f[now]]);
now=from[f[now]];
}
if(ans+d[T]*flow<=0)
{
ans+=d[T]*flow;
maxflow+=flow;
}
else
{
maxflow+=fabs(ans)/fabs(d[T]);
return 1;
}
now=T;
while(now!=S)
{
c[f[now]]-=flow;
c[f[now]^1]+=flow;
now=from[f[now]];
}
return 0;
}
bool SPFA()
{
for(int i=1;i<=T;i++)
{
d[i]=INF;
}
d[S]=0;
q.push(S);
vis[S]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i;i=next[i])
{
if(!c[i])
{
continue;
}
if(d[to[i]]>d[now]+v[i])
{
d[to[i]]=d[now]+v[i];
f[to[i]]=i;
if(!vis[to[i]])
{
q.push(to[i]);
vis[to[i]]=1;
}
}
}
}
return d[T]!=INF;
}
void find_max()
{
while(SPFA())
{
if(result())
{
break;
}
}
}
bool check(int x,int y)
{
if(x<y)
{
swap(x,y);
}
if(x%y)
{
return false;
}
int d=x/y;
for(int i=2;i*i<=d;i++)
{
if(d%i==0)
{
return false;
}
}
return true;
}
int main()
{
scanf("%d",&n);
S=2*n+1,T=S+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&B[i]);
add(S,i,0,B[i]);
add(i+n,T,0,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(check(A[i],A[j]))
{
add(i,n+j,-1ll*C[i]*C[j],1<<30);
add(j,n+i,-1ll*C[i]*C[j],1<<30);
}
}
}
find_max();
printf("%d",maxflow/2);
}