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. 「SCOI2007」蜥蜴 - 网络流

    在一个 r r c c 列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外。

    每行每列中相邻石柱的距离为 1 1 ,蜥蜴的跳跃距离是 d d ,即蜥蜴可以跳到平面曼哈顿距离不超过 d d 的任何一个石柱上。

    石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减 1 1 (如果仍然落在地图内部,则到达的石柱高度不变),如果该石柱原来高度为 1 1 ,则蜥蜴离开后消失。以后其他蜥蜴不能落脚。

    任何时刻不能有两只蜥蜴在同一个石柱上。

    于  BZOJ, Dinic, SCOI, 网络流 继续阅读

  3. 「NOI2015」小园丁与老司机 - DP + 上下界网络流

    在坐标系的第一象限内有 n n 个点。

    1. 从原点开始,每次向左、右、上、左上 45 45 ^ \circ 、右上 45 45 ^ \circ 任意一个方向走到第一个未到过的点,重复这个过程,求最多能经过多少点;
    2. 求 (1) 中的一个最优方案;
    3. 对于 (1) 中的所有最优方案,其所有上、左上 45 45 ^ \circ 、右上 45 45 ^ \circ 的边组成了一个 DAG,求该 DAG 的可重叠最小路径覆盖。

    于  BZOJ, DP, Dinic, NOI, 上下界网络流, 网络流 继续阅读

  4. 「ZJOI2009」狼和羊的故事 - 最小割

    Orez 的羊狼圈可以看作一个 n×m n \times m 个矩阵格子,这个矩阵的边缘已经装上了篱笆。他决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez 发现狼和羊都有属于自己领地,Orez 想要添加篱笆的尽可能的短。篱笆不能改变狼羊的所属领地,篱笆必须修筑完整,也就是说必须修建在单位格子的边界上并且不能只修建一部分。

    于  BZOJ, Dinic, ZJOI, 最小割, 网络流 继续阅读

  5. 「BZOJ 2132」圈地计划 - 最小割

    对于第 i i 行第 j j 列的区域,建造商业区将得到 Ai, j A_{i,\ j} 收益,建造工业区将得到 Bi, j B_{i,\ j} 收益。另外不同的区域连在一起可以得到额外的收益,即如果区域 (i, j) (i,\ j) 相邻(相邻是指两个格子有公共边)有 K K 块(显然 K K 不超过 4 4 )类型不同于 (i, j) (i,\ j) 的区域,则这块区域能增加 K×Ci, j K \times C_{i,\ j} 收益。求最大收益。

    于  BZOJ, Dinic, 最小割, 网络流 继续阅读

  6. 「POI2005」Kos-Dicing - 二分答案 + 网络流

    Dicing 是一个两人玩的游戏,人们专门成立了这个游戏的一个俱乐部,俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人。有一个人想知道比赛以后赢的最多的那个家伙最少会赢多少场。

    于  BZOJ, Dinic, POI, 二分答案, 网络流 继续阅读

  7. 「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, 网络流, 费用流 继续阅读

  8. 「BZOJ 1585」Earthquake Damage 2 - 最小割

    农场里有 P P 个牧场,有 C C 条无向道路连接着他们,第 i i 条道路连接着两个牧场 Ai A_i Bi B_i ,注意可能有很多条道路连接着相同的 Ai A_i Bi B_i ,并且 Ai A_i 有可能和 Bi B_i 相等。Farmer John 在 1 1 号牧场里。某些牧场被损坏,C C 条道路没有一条损坏。有 N N 头奶牛,第 i i 头奶牛报告一个整数 Ri R_i ,代表第 Ri R_i 个牧场没有损毁,但不能够从第 Ri R_i 个牧场经过一些没有损坏的牧场到达 1 1 号牧场。现在 Farmer John 想知道,最少有多少损坏的牧场。

    于  BZOJ, Dinic, USACO, 最小割, 网络流 继续阅读

  9. 「CEOI2008」Order - 最小割

    N N 个工作,M M 种机器,每种机器你可以租或者买过来。每个工作(可以不做)包括若干道工序,每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。求最大利润。

    于  BZOJ, Dinic, 最小割, 网络流 继续阅读

  10. 「BZOJ 1711」Dining - 网络流

    每一头牛只喜欢吃一些食品和饮料而别的一概不吃。农夫做了 F F 1F100 1 \leq F \leq 100 )种食品并准备了 D D 1D100 1 \leq D \leq 100 )种饮料。N N 1N100 1 \leq N \leq 100 )头牛都以决定了是否愿意吃某种食物和喝某种饮料。

    农夫想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料。

    每一件食物和饮料只能由一头牛来用。

    于  BZOJ, Dinic, USACO, 网络流 继续阅读