Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SDOI2016」数字配对 - 费用流

    n n 种数字,第 i i 种数字是 ai a_i 、有 bi b_i 个,权值是 ci c_i

    若两个数字 ai a_i aj a_j 满足,ai a_i aj a_j 的倍数,且 aiaj \frac{a_i}{a_j} 是一个质数,那么这两个数字可以配对,并获得 ci×cj c_i \times c_j 的价值。

    一个数字只能参与一次配对,可以不参与配对。
    在获得的价值总和不小于 0 0 的前提下,求最多进行多少次配对。

    于  BZOJ, COGS, Edmonds-Karp, SDOI, 二分答案, 数论, 素数判定, 线性筛, 网络流, 费用流 继续阅读