P4068-[SDOI2016]数字配对
题目:
题目描述:
有 n 种数字，第 i 种数字是 $a_i$、有 $b_i$ 个，权值是 $c_i$。
若两个数字 $a_i$、$a_j$ 满足，$a_i$ 是 $a_j$ 的倍数，且 $a_i/a_j$ 是一个质数，
那么这两个数字可以配对，并获得 $c_i \times c_j$ 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
输入格式:
第一行一个整数 n。
第二行 n 个整数 $a_1,a_2,\cdots,a_n$。
第三行 n 个整数 $b_1,b_2,\cdots,b_n$。
第四行 n 个整数 $c_1,c_2,\cdots,c_n$。
输出格式:
一行一个数，最多进行多少次配对
样例:
样例输入 1:
1
2
3
4
| 3
2 4 8
2 200 7
-1 -2 1
|
样例输出 1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| #include "ybwhead/ios.h"
#define int long long
int n;
const int maxn = 2e2 + 10;
const int maxm = 5e5 + 10;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int a[maxn], b[maxn], c[maxn];
int tot = 1, head[maxn];
struct edge
{
int u, v, nxt;
long long w, x;
} e[maxm];
void __ADD(int u, int v, long long w, int x)
{
e[++tot] = (edge){u, v, head[u], w, x};
head[u] = tot;
}
void add(int u, int v, long long w, int x)
{
__ADD(u, v, w, x);
__ADD(v, u, 0, -x);
}
int S, T;
int prime(int n)
{
int x = 0;
for (int i = 2; i * i <= n; i++)
{
while (n % i == 0)
x++, n /= i;
}
if (n > 1)
return x + 1;
return x;
}
int cnt[maxn];
long long dis[maxn];
queue<int> q;
int vis[maxn];
int frm[maxm];
int bfs()
{
for (int i = 0; i <= n + 1; i++)
vis[i] = 0, dis[i] = -inf;
q.push(S);
dis[S] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (e[i].w && dis[u] + e[i].x > dis[v])
{
dis[v] = dis[u] + e[i].x;
frm[v] = i;
if (!vis[v])
q.push(v), vis[v] = 1;
}
// yout << e[i].v << ' ' << e[i].u << " " << e[i].w << endl;
}
}
// yout << T << ' ' << dis[T] << endl;
return dis[T] > -inf;
}
long long sum, ans;
int check()
{
long long fl = inf, delta;
for (int i = frm[T]; i; i = frm[e[i].u])
fl = min(fl, e[i].w);
delta = dis[T] * fl;
if (sum + delta < 0)
{
ans += sum / (-dis[T]);
return 0;
}
else
{
sum += delta;
ans += fl;
for (int i = frm[T]; i; i = frm[e[i].u])
e[i].w -= fl, e[i ^ 1].w += fl;
return 1;
}
}
signed main()
{
yin >> n;
for (int i = 1; i <= n; i++)
yin >> a[i];
for (int i = 1; i <= n; i++)
yin >> b[i];
for (int i = 1; i <= n; i++)
yin >> c[i];
S = 0, T = n + 1;
for (int i = 1; i <= n; i++)
cnt[i] = prime(a[i]);
for (int i = 1; i <= n; i++)
{
if (cnt[i] & 1)
add(S, i, b[i], 0);
else
add(i, T, b[i], 0);
}
for (int i = 1; i <= n; i++)
{
if (!(cnt[i] & 1))
continue;
for (int j = 1; j <= n; j++)
{
if (cnt[i] == cnt[j] + 1 && a[i] % a[j] == 0)
add(i, j, inf, 1ll * c[i] * c[j]);
if (cnt[i] == cnt[j] - 1 && a[j] % a[i] == 0)
add(i, j, inf, 1ll * c[i] * c[j]);
}
}
// puts("!!!");
while (bfs() && check())
;
yout << ans << endl;
return 0;
}
|