Menci

眉眼如初,岁月如故

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


  1. 「SDOI2014」LIS - 最小割 + 网络流退流

    给定序列 A A ,序列中的每一项 Ai A_i 有删除代价 Bi B_i 和附加属性 Ci C_i 。请删除若干项,使得 A A 的最长上升子序列长度减少至少 1 1 ,且付出的代价之和最小,并输出方案。

    如果有多种方案,请输出将删去项的附加属性排序 Ci C_i 之后,字典序最小的一种。

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

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

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

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

  3. 「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, 最小割, 网络流 继续阅读

  4. 「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, 最小割, 网络流 继续阅读

  5. 「CEOI2008」Order - 最小割

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

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

  6. 「BZOJ 3894」文理分科 - 最大权闭合图

    小 P 所在的班级要进行文理分科。他的班级可以用一个 n×m n \times m 的矩阵进行描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到:

    1. 如果第 i i 行第 j j 列的同学选择了文科,则他将获得 a[i][j] a[i][j] 的满意值,如果选择理科,将获得 b[i][j] b[i][j] 的满意值。
    2. 如果第 i i 行第 j j 列的同学选择了文科,并且他相邻(两个格子相邻当且仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开心,所以会增加 A[i][j] A[i][j] 的满意值。
    3. 如果第 i i 行第 j j 列的同学选择了理科,并且他相邻的同学全部选择了理科,则增加 B[i][j] B[i][j] 的满意值。

    小 P 想知道,大家应该如何选择,才能使所有人的满意值之和最大。请告诉他这个最大值。

    于  BZOJ, Dinic, 最大权闭合图, 最小割, 网络流 继续阅读

  7. 「BZOJ 2127」happiness - 最大权闭合图

    高一一班的座位表是个 n×m n \times m 的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。如何分配可以使得全班的喜悦值总和最大?

    于  BZOJ, Dinic, 最大权闭合图, 最小割, 网络流 继续阅读

  8. 「BZOJ 3438」小 M 的作物 - 最大权闭合图

    小 M 有耕地 A A B B ,有 n n 中作物的种子,第i种作物种植在 A A 中种植可以获得 ai a_i 的收益,在 B B 中种植可以获得 bi b_i 的收益。
    共有 m m 种作物组合,第 i i 个组合中的作物共同种在 A A 中可以获得 c1i c_{1_i} 的额外收益,共同总在 B B 中可以获得 c2i c_{2_i} 的额外收益。
    求最大收益。

    于  BZOJ, Dinic, 最大权闭合图, 最小割, 网络流 继续阅读

  9. 「SHOI2007」善意的投票 - 最小割

    幼儿园里有 n n 个小朋友打算通过投票来决定睡不睡午觉。他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。每位小朋友应该怎样投票,才能使冲突数最小?

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

  10. 「BZOJ 3275」Number - 最小割

    N N 个正整数,需要从中选出一些数,使这些数的和最大。

    若两个数 a, b a,\ b 同时满足以下条件,则 a, b a,\ b 不能同时被选。

    1. 存在正整数 c c ,使 a2+b2=c2 a ^ 2 + b ^ 2 = c ^ 2
    2. gcd(a, b)=1 \gcd(a,\ b) = 1

    于  BZOJ, Dinic, 二分图染色, 最小割, 网络流 继续阅读