Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 3280」小 R 的烦恼 - 费用流

    程设老师最近要进行一项邪恶的实验,这个实验一共持续 n n 天,第 i i 天需要 ai a_i 个研究生来给他搬砖。研究生毕竟也是人,所以雇佣研究生是需要钱的,机智的程设老师已经联系好了 m m 所大学,第 j j 所大学共有 lj l_j 个研究生,同时雇佣这所大学的一个研究生需要 pj p_j 元钱。

    一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生,毫无疑问,就不能再进行工作了。但是机智的老师早早联系好了 k k 家医院,第 i i 家医院医治一个濒死的研究生需要 di d_i 天,并且需要 qi q_i 元钱。

    于  BZOJ, Edmonds-Karp, 网络流, 费用流 继续阅读

  2. 「POI2006」Szk-Schools - 费用流

    有一个长度为 n n 的序列 ai a_i ,每个数都在 [1, n] [1,\ n] 之间,要求把这些数变成一个 n n 的排列:

    1. ai a_i 可以被改成 [li, ri] [l_i,\ r_i] 之间的数;
    2. ai a_i 改变为 x x 的花费为 k×aix k \times | a_i - x |

    求是否可行及最小花费。

    于  BZOJ, Edmonds-Karp, POI, 网络流, 费用流 继续阅读

  3. 「SDOI2009」晨跑 - 费用流

    现在给出一张地图,地图中包含 N N 个十字路口和 M M 条街道,Elaxia 只能从一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia 每天从寝室出发跑到学校,保证寝室编号为 1 1 ,学校编号为 N N 。 Elaxia 的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路口。
    他希望在一个周期内跑的路程尽量短,但是又希望训练周期包含的天数尽量长。

    于  BZOJ, Edmonds-Karp, SDOI, 网络流, 费用流 继续阅读

  4. 「ZJOI2010」网络扩容 - 网络流 + 费用流

    给定一张有向图,每条边都有一个容量 C C 和一个扩容费用 W W 。这里扩容费用是指将容量扩大 1 1 所需的费用,求

    1. 在不扩容的情况下,1 1 N N 的最大流;
    2. 1 1 N N 的最大流增加 K K 所需的最小扩容费用。

    于  BZOJ, Dinic, Edmonds-Karp, ZJOI, 网络流, 费用流 继续阅读

  5. 「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, 二分答案, 数论, 素数判定, 线性筛, 网络流, 费用流 继续阅读

  6. 「AHOI2014」支线剧情 - 费用流

    游戏中有 N N 个剧情点,由 1 1 N N 编号,第 i i 个剧情点可以经过不同的支线剧情,前往 Ki K_i 种不同的新的剧情点。当然如果为 0 0 ,则说明 i i 号剧情点是游戏的一个结局了。

    开始处在 1 1 号剧情点。任何一个剧情点都是从 1 1 号剧情点可达的。从任意剧情点出发,都不能再回到这个剧情点。要想回到之前的剧情点,唯一的方法就是开始新的游戏,回到 1 1 号剧情点。可以在任何时刻退出游戏并重新开始。求花费最少的时间,看完所有不同的支线剧情。

    于  AHOI, BZOJ, Edmonds-Karp, 上下界网络流, 网络流, 费用流 继续阅读

  7. 「SCOI2007」修车 - 费用流

    同一时刻有 N N 位车主带着他们的爱车来到了汽车维修中心。维修中心共有 M M 位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这 M M 位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。

    顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

    于  BZOJ, CodeVS, Edmonds-Karp, SCOI, 图论, 网络流, 费用流 继续阅读

  8. 「SDOI2010」星际竞速 - 费用流

    大赛要求车手们从一颗与这 N N 颗行星之间没有任何航路的天体出发,访问这 N N 颗行星每颗恰好一次。超能电驴有两种移动模式:高速航行模式和能力爆发模式。在高速航行模式下,超能电驴会沿星际航路高速航行。在能力爆发模式下,经过一段时间的定位之后,它能瞬间移动到任意一个行星。在使用高速航行模式的时候,只能由每个星球飞往引力比它大的星球,否则赛车就会发生爆炸。求完成比赛的最少时间。

    于  BZOJ, Edmonds-Karp, SDOI, 图论, 网络流, 费用流 继续阅读

  9. 「COGS 741」负载平衡 - 费用流

    G 公司有 n 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 n 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。

    于  COGS, Edmonds-Karp, 图论, 网络流, 网络流 24 题, 费用流 继续阅读

  10. 「COGS 740」分配问题 - 二分图最大权匹配

    n 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 c[i][j]。试设计一个将 n 件工作分配给 n 个人做的分配方案,使产生的总效益最大。

    于  COGS, Edmonds-Karp, 二分图匹配, 图论, 网络流, 网络流 24 题, 费用流 继续阅读