【BZOJ4514】【SDOI2016】数字配对 [费用流]

数字配对

Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]

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

Solution

　　显然是一个费用流，并且这可以是一个二分图，由于 ai/aj 要是质数，那显然可以根据质因子个数的奇偶分类。

　　然后跑一跑最大费用最大流。判断一下值要>=0即可统计入答案。mmpBearChild查了一个下午错，发现是INF开小了qaq。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long s64;

 const int ONE = *;

 const int INF = ;

 int n;

 int a[ONE], b[ONE], c[ONE];

 s64 dist[ONE];

 int vis[ONE], q[ONE*], pre[ONE];

 int first[ONE], go[ONE], next[ONE], pas[ONE], from[ONE], tot;

 int pNum[ONE];

 int odd[ONE],Onum, eve[ONE],Enum;

 int S, T, Ans;

 int prime[ONE], isp[ONE], p;

 s64 Val, w[ONE];

 int get()

 {

         int res=,Q=;char c;

         while( (c=getchar())< || c> )

         if(c=='-')Q=-;

         res=c-;

         while( (c=getchar())>= && c<= )

         res=res*+c-;

         return res*Q;

 }

 void Getp(int MaxN)

 {

         for(int i=; i <= MaxN; i++)

         {

             if(!isp[i]) prime[++p] = i;

             for(int j=; j <= prime[p], i*prime[j] <= MaxN; j++)

             {

                 isp[i * prime[j]] = ;

                 if(i % prime[j] == ) break;

             }

         }

 }

 int Factor(int x)

 {

         int res = ;

         while(x != )

         {

             for(int i=; i<=p; i++)

             if(x % prime[i] == )

             {

                 x /= prime[i];

                 res++;

                 break;

             }

         }

         return res;

 }

 int PD(int x, int y)

 {

         if(x > y) swap(x, y);

         if(x== || y== || y%x!=) return ;

         x = y / x;

         for(int i=; i<x; i++)

         if(x % i == ) return ;

         return ;

 }

 int Add(int u, int v, int flow, s64 z)

 {

         next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  pas[tot]=flow;  w[tot]=z;   from[tot]=u;

         next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  pas[tot]=;     w[tot]=-z;  from[tot]=v;

 }

 bool Bfs()

 {

         for(int i=S; i<=T; i++) dist[i] = -1e18;

         int tou = , wei = ;

         q[] = S;   vis[S] = ; dist[S] = ;

         while(tou < wei)

         {

             int u = q[++tou];

             for(int e=first[u]; e; e=next[e])

             {

                 int v=go[e];

                 if(dist[v] < dist[u] + w[e] && pas[e])

                 {

                     dist[v] = dist[u] + w[e];

                     pre[v] = e;

                     if(!vis[v])

                     {

                         q[++wei] = v;

                         vis[v] = ;

                     }

                 }

             }

             vis[u] = ;

         }

         return dist[T] != -1e18;

 }

 void Deal()

 {

         int x = INF;

         for(int e=pre[T]; e; e=pre[from[e]]) x = min(x, pas[e]);

         if(Val + dist[T] * x >= )

         {

             for(int e=pre[T]; e; e=pre[from[e]])

             {

                 pas[e] -= x;

                 pas[((e-)^)+] += x;

             }

             Val += dist[T] * x;

             Ans += x;

             return;

         }

         printf("%d", Ans - Val / dist[T]);

         exit();

 }

 int main()

 {

         Getp(ONE);

         n = get();

         for(int i=; i<=n; i++) a[i] = get(), pNum[i] = Factor(a[i]);

         for(int i=; i<=n; i++) b[i] = get();

         for(int i=; i<=n; i++) c[i] = get();

         S = ; T = n+;

         for(int i=; i<=n; i++)

         {

             if(pNum[i] & ) Add(S,i, b[i],), odd[++Onum] = i;

             else Add(i,T, b[i],), eve[++Enum] = i;

         }

         for(int i=; i<=Onum; i++)

         for(int j=; j<=Enum; j++)

         {

             int x = odd[i], y = eve[j];

             if( PD(a[x], a[y]) )

                 Add(x,y, INF,(s64)c[x]*c[y]);

         }

         while(Bfs()) Deal();

         printf("%d", Ans - Val / dist[T]);

 }

巴特西