bzoj4514 [Sdoi2016]数字配对

Description

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

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

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

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

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

Input

第一行一个整数 n。

第二行 n 个整数 a1、a2、……、an。

第三行 n 个整数 b1、b2、……、bn。

第四行 n 个整数 c1、c2、……、cn。

Output

一行一个数，最多进行多少次配对

Sample Input

3
2 4 8
2 200 7
-1 -2 1

Sample Output

HINT

n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5

正解：费用流。

这题的费用流模型还是比较显然的，不过有两个要注意的地方。

首先这题需要建成二分图的模型，所以每个点的流量肯定会乘$2$，如果直接连可能会导致有些点多用了流量。对于这种情况，我们在每个$i->j$的连边时，把$j->i$也连边，最后把流量除以$2$，就能解决这个问题了。

还有一个问题，题目是问的费用$>=0$的最大流，首先我们肯定要把费用取反，转成最小费用最大流。然后我们可以在每次增广时加一个特判，如果之前增广的费用+当前费用$>0$，那么我们直接取使得费用$<=0$的最大流量就行了。因为费用流每次都是找最短路增广，所以这样做是对的。

 //It is made by wfj_2048~

 #include <algorithm>

 #include <iostream>

 #include <complex>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #define inf (1LL<<60)

 #define N (3010)

 #define il inline

 #define RG register

 #define ll long long

 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

 using namespace std;

 struct edge{ ll nt,to,flow,cap,dis; }g[];

 ll head[N],dis[N],vis[N],f[N],p[N],fa[N],a[N],b[N],c[N];

 ll q[],n,S,T,flow,cost,num=;

 il ll gi(){

     RG ll x=,q=; RG char ch=getchar();

     while ((ch<'' || ch>'') && ch!='-') ch=getchar();

     if (ch=='-') q=-,ch=getchar();

     while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

     return q*x;

 }

 il void insert(RG ll from,RG ll to,RG ll cap,RG ll cost){

     g[++num]=(edge){head[from],to,,cap,cost},head[from]=num; return;

 }

 il ll bfs(RG ll S,RG ll T){

     for (RG ll i=;i<=T;++i) dis[i]=inf;

     RG ll h=,t=; q[t]=S,dis[S]=,vis[S]=,f[S]=inf;

     while (h<t){

     RG ll x=q[++h],v;

     for (RG ll i=head[x];i;i=g[i].nt){

         v=g[i].to;

         if (dis[v]>dis[x]+g[i].dis && g[i].cap>g[i].flow){

         dis[v]=dis[x]+g[i].dis,fa[v]=x,p[v]=i;

         f[v]=min(f[x],g[i].cap-g[i].flow);

         if (!vis[v]) vis[v]=,q[++t]=v;

         }

     }

     vis[x]=;

     }

     if (dis[T]==inf) return ;

     if (cost+dis[T]*f[T]>){ //费用>0特判

     RG ll x=-cost/dis[T];

     flow+=x; return ;

     }

     flow+=f[T],cost+=dis[T]*f[T];

     for (RG ll i=T;i!=S;i=fa[i])

     g[p[i]].flow+=f[T],g[p[i]^].flow-=f[T];

     return ;

 }

 il ll isprime(RG ll x){

     if (x== || x==) return ;

     if (!(x&)) return x==;

     for (RG ll i=;i*i<=x;++i)

     if (!(x%i)) return ;

     return ;

 }

 il void work(){

     n=gi(),S=*n+,T=*n+;

     for (RG ll i=;i<=n;++i) a[i]=gi();

     for (RG ll i=;i<=n;++i) b[i]=gi();

     for (RG ll i=;i<=n;++i) c[i]=gi();

     for (RG ll i=;i<=n;++i){

     insert(S,i,b[i],),insert(i,S,,);

     insert(n+i,T,b[i],),insert(T,n+i,,);

     }

     for (RG ll i=;i<=n;++i)

     for (RG ll j=;j<=n;++j){

         if (a[i]%a[j]) continue;

         if (isprime(a[i]/a[j])){

         insert(i,n+j,inf,-c[i]*c[j]),insert(n+j,i,,c[i]*c[j]);

         insert(j,n+i,inf,-c[i]*c[j]),insert(n+i,j,,c[i]*c[j]);

         //防止多余流量影响结果

         }

     }

     while (bfs(S,T)); printf("%lld\n",flow>>); return;

 }

 int main(){

     File("match");

     work();

     return ;

 }

秒客网