笔记

网络流

网络流的总结, 以建模为主. 有些地方比较简略, 原因是不甚了解或者写这篇文章的时间有限.

最大流

二分图最大匹配

二分图最大匹配用最大流建模, 二分图最小点覆盖用最小割建模. 它们建出来的图是一样的. 最大流 = 最小割. 我们用这种方式证明了 König定理......

DAG 的最小路径覆盖

在 DAG 中找出一些顶点不相交的路径, 使之覆盖图中所有顶点. 求路径条数的最小值.

最小化路径条数, 即最大化路径长度之和. 每个点只能向一个点连边, 也只能接受一个点连过来的边. 把每个点拆成入,出两个, 那么, 我们求的是入点和出点之间的最大匹配.

非 DAG 中, 这种方法无法避免一个环被选中.

费用流

最大权不相交路径

S向原图中每个点连边, 每个点向T连边. 保留原图中的边, 容量为 1, 费用为边权. 用总流量限制路径条数.

区间 K 覆盖

数轴上有一些左闭右开区间, 选出权和尽量大的一些区间, 使得任意一个数最多被 K 个区间覆盖.

Key: 每个合法方案可以被分解成不超过 K 组不相交区间.

i 向 i+1 连边, 流量为 K 或inf, 费用为 0. 对于 [li,ri), 从 li 向 ri 连边, 流量为 1, 费用为 wi. 求最左点到最右点的最小费用最大流.

线性规划

  • [NOI 2008] 志愿者招募

最小割

二分图最小点权覆盖

S向左部每个点连边, 右部每个点向T连边, 保留原图中的边, 容量inf. 方案: 左部在S集中的点 + 右部在T集中的点.

二分图最大点权独立集

先假设所有点都选, 问题转化为选出点权之和最小的点集, 使得每条边至少有一个端点被选中, 这就是二分图最小点权覆盖的定义.

二分图中, 最大边独立集 (匹配) = 最小点覆盖, 最大点独立集 = 最小边覆盖.

距离限制模型

每个变量有取值范围, 一些限制: u-v ≤ D. 限取整数, 且范围不大.

每个变量, 对每个取值建一个点, 从小到大串起来, S向第一个点连边, 最后一个点向T连边. v 向 u-D 连边 (如果存在).

  • [bzoj 3144] [Hnoi2013]切糕

最大权闭合子图

S向所有正权点连边, 所有负权点向T连边, 边权均为点权的绝对值. 保留原图中的边, 容量为inf. 答案 = 正权点和-最小割. 方案: S集中的点. - [NOI 2009] 植物大战僵尸 注意被环保护的点也是无敌的. - [bzoj 4873] [Shoi2017]寿司餐厅 - [bzoj 1391] [Ceoi2008]order N 个任务, M 种机器. 每个任务有收益, 且需要一些机器, 这个任务租用每台机器有自己的价格. 也可以选择不完成该任务, 或者购买机器. 求最大利润. (1≤N≤1200,1≤M≤1200) 改inf为租赁价格. - [Codeforces #181 Div.1 E] Biologist n 个已有初值的 01 变量, 改变一个变量花费 vi. m 种收益: 某个集合中的变量均为 0/1, 获得 wi (wi > 0). 求最大收益. 先使所有变量为 0. 一个 0->1, 可能导致全 0 收益失效. 一堆 0->1, 可能获得全 1 收益. 收益是正数, 所以可用最大权闭合子图建模: 全 1 收益向变量连边, 变量向全 0 损失连边. - [bzoj 3684] 文理分科 n*m 的矩阵 a, 给每个格子赋上 0 或 1. a[i][j]=0 获得 a[i][j] 的价值, a[i][j]=1 获得 b[i][j] 的价值, (i,j) 和与它相邻的格子均为 0 获得 Sa[i][j] 的价值, (i,j) 和与它相邻的格子均为 1 获得 Sb[i][j] 的价值. 求最大收益. (相邻指四连通, n,m≤100, 所有数≤500) 同前面一题.

二元关系

一些元素, 每个在两种状态中选且仅选一个, 选择可以有代价. 有一些二元关系 (ui,vi), 描述 ui,vi 取值的关系产生的额外代价. 所有代价累加, 求最小总代价.

通用解法: 列方程. 解出来容量为 0 的边可以省去. 有时解出无法避免的负数, 此时需要二分图的条件.

  • [bzoj 1934] [Shoi2007]Vote 善意的投票 每个人有一个意见 xi (0 或 1). 投和自己意见相反的票, 冲突 +1. 有一些 (双向) 朋友关系. 投和自己朋友相反的票, 冲突数 +1. 求最小冲突数.
  • [bzoj 2127] happiness
  • [Topcoder srm 558 div1] t3 n*m 的矩阵, 每个格子可以放一个石头. 每个石头花费 c. 如果一个格子放了石头, 或它周围的格子都放了石头, 收益 v. 求最大 收益-花费. (c,v > 0, 2≤n,m≤20) 先把 v 加起来, 化最大为最小. x[i][j] 表示 (i,j) 是否放了石头. "周围的格子"? 由于代价是累加的, 所以不好凭二元关系直接处理. 对每个格子引入一个新变量 x'[i][j], 表示 (i,j) 周围的格子是否都放了石头. x=1代价为 c. x=x'=0代价为 v. 设 y 是与 x 相邻的一个格子, x'=1,y=0代价inf.

平面图最小割

S向T连一条虚拟边, 建平面图的对偶图. 虚拟边形成的两个新的面为S*,T*. 平面图最小割 = 对偶图最短路. - [bzoj 1001] [BeiJing2006]狼抓兔子 - [NOI 2010] 海拔 海拔高度非 0 即 1, 且所有 0 与左上角连通, 所有 1 与右下角连通. 那么, 只用求出分界线的长度, 即左上到右下的最小割. 或者, 转成对偶图, 左下到右上的最短路. 注意边是有向的.

上下界网络流

有下界无源汇可行流

新建附加源S', 附加汇T'. 对于一条范围为 [L,R] 的边 (u,v), 用这样三条下界为 0 的边代替: (S',v), 容量为 L; (u,T'), 容量为 L; (u,v) 容量 R-L. 有解当且仅当和附加源汇关联的边满流.

有下界有源汇最大流

T向S连一条容量inf的边, 网络转化为无源汇的. 用上面的方法求出一个可行流, 然后去掉(T,S)和附加源汇, 跑S-T最大流. 答案 = (T,S)的流量 + 最大流.

有下界有源汇最小流

同上, 只是换作跑T-S最大流. 答案 = (T,S)的流量 - 最大流.

综合

二分

线段树 / ST 表