数字配对
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
2 4 8
2 200 7
-1 -2 1
Sample Output
4
HINT
n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5
Solution
显然是一个费用流，并且这可以是一个二分图，由于 ai/aj 要是质数，那显然可以根据质因子个数的奇偶分类。
然后跑一跑最大费用最大流。判断一下值要>=0即可统计入答案。mmpBearChild查了一个下午错，发现是INF开小了qaq。
Code
1 #include<iostream>
2 #include<string>
3 #include<algorithm>
4 #include<cstdio>
5 #include<cstring>
6 #include<cstdlib>
7 #include<cmath>
8 #include<map>
9 using namespace std;
10 typedef long long s64;
11
12 const int ONE = 205*205;
13 const int INF = 2147483640;
14
15 int n;
16 int a[ONE], b[ONE], c[ONE];
17 s64 dist[ONE];
18 int vis[ONE], q[ONE*10], pre[ONE];
19 int first[ONE], go[ONE], next[ONE], pas[ONE], from[ONE], tot;
20 int pNum[ONE];
21 int odd[ONE],Onum, eve[ONE],Enum;
22 int S, T, Ans;
23 int prime[ONE], isp[ONE], p;
24 s64 Val, w[ONE];
25
26 int get()
27 {
28 int res=1,Q=1;char c;
29 while( (c=getchar())<48 || c>57 )
30 if(c=='-')Q=-1;
31 res=c-48;
32 while( (c=getchar())>=48 && c<=57 )
33 res=res*10+c-48;
34 return res*Q;
35 }
36
37 void Getp(int MaxN)
38 {
39 for(int i=2; i <= MaxN; i++)
40 {
41 if(!isp[i]) prime[++p] = i;
42 for(int j=1; j <= prime[p], i*prime[j] <= MaxN; j++)
43 {
44 isp[i * prime[j]] = 1;
45 if(i % prime[j] == 0) break;
46 }
47 }
48 }
49
50 int Factor(int x)
51 {
52 int res = 0;
53 while(x != 1)
54 {
55 for(int i=1; i<=p; i++)
56 if(x % prime[i] == 0)
57 {
58 x /= prime[i];
59 res++;
60 break;
61 }
62 }
63 return res;
64 }
65
66 int PD(int x, int y)
67 {
68 if(x > y) swap(x, y);
69 if(x==0 || y==0 || y%x!=0) return 0;
70 x = y / x;
71 for(int i=2; i<x; i++)
72 if(x % i == 0) return 0;
73 return 1;
74 }
75
76 int Add(int u, int v, int flow, s64 z)
77 {
78 next[++tot]=first[u]; first[u]=tot; go[tot]=v; pas[tot]=flow; w[tot]=z; from[tot]=u;
79 next[++tot]=first[v]; first[v]=tot; go[tot]=u; pas[tot]=0; w[tot]=-z; from[tot]=v;
80 }
81
82 bool Bfs()
83 {
84 for(int i=S; i<=T; i++) dist[i] = -1e18;
85 int tou = 0, wei = 1;
86 q[1] = S; vis[S] = 1; dist[S] = 0;
87 while(tou < wei)
88 {
89 int u = q[++tou];
90 for(int e=first[u]; e; e=next[e])
91 {
92 int v=go[e];
93 if(dist[v] < dist[u] + w[e] && pas[e])
94 {
95 dist[v] = dist[u] + w[e];
96 pre[v] = e;
97 if(!vis[v])
98 {
99 q[++wei] = v;
100 vis[v] = 1;
101 }
102 }
103 }
104 vis[u] = 0;
105 }
106 return dist[T] != -1e18;
107 }
108
109 void Deal()
110 {
111 int x = INF;
112 for(int e=pre[T]; e; e=pre[from[e]]) x = min(x, pas[e]);
113 if(Val + dist[T] * x >= 0)
114 {
115 for(int e=pre[T]; e; e=pre[from[e]])
116 {
117 pas[e] -= x;
118 pas[((e-1)^1)+1] += x;
119 }
120 Val += dist[T] * x;
121 Ans += x;
122 return;
123 }
124 printf("%d", Ans - Val / dist[T]);
125 exit(0);
126 }
127
128 int main()
129 {
130 Getp(ONE);
131 n = get();
132 for(int i=1; i<=n; i++) a[i] = get(), pNum[i] = Factor(a[i]);
133 for(int i=1; i<=n; i++) b[i] = get();
134 for(int i=1; i<=n; i++) c[i] = get();
135
136 S = 0; T = n+1;
137 for(int i=1; i<=n; i++)
138 {
139 if(pNum[i] & 1) Add(S,i, b[i],0), odd[++Onum] = i;
140 else Add(i,T, b[i],0), eve[++Enum] = i;
141 }
142
143 for(int i=1; i<=Onum; i++)
144 for(int j=1; j<=Enum; j++)
145 {
146 int x = odd[i], y = eve[j];
147 if( PD(a[x], a[y]) )
148 Add(x,y, INF,(s64)c[x]*c[y]);
149 }
150
151 while(Bfs()) Deal();
152 printf("%d", Ans - Val / dist[T]);
153 }