Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

08/12
11:30
费用流

[bzoj 4514] [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   ♦♦♦♦♦♦

4

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

每次跑最大费用最大流,直到费用<0时停止

c++:

pascal:

 

[bzoj 4514] [Sdoi2016]数字配对