匹配

给定二分图，求是否存在 \(k\) 个完全不同的完备匹配。

• 每个点度数为 \(k\) 等价于题目要求。
• 题目转化为求是否存在每个点度数都为 \(k\) 的子图
• 跑 \(k\) 次匈牙利即可。

SCOI2012 奇怪的游戏

\(n\times m\) 的矩阵上，每处有权值。一次操作可以将相邻的位置同时加 \(1\)，求至少要加多少次处处相等。

• 如果知道最终的值，直接黑白染色二分图即可。
• 对于 \(2\not|nm\)，最终的值可以算出来。
• 否则，二分最终值大小。

TheTilesDivOne

\(n\times m\) 的黑白染色的有障碍矩阵上，最多能放多少个 L 型。L 型指大小为 \(3\) 的、拐点在黑色上的连通块。

• 三分图模型：黑白染色分两类，在将黑点按行数奇偶分两类。

CurvyonRails

\(n\times m\) 的有障碍矩阵上，有关键点，用若干环将其完全覆盖，不可重复覆盖。求关键点是拐点的最大值。

• 环是度数全为 \(2\) 的图，所以度数全为 \(2\) 则一定是环森林。
• 先假设关键点全是拐点，题目转化为求最少有多少个关键点的两条边同行或同列。
• 黑白染色，每个点有 \(4\) 条连边 \(2\) 份流量。如果同时流行或同时流列就产生 \(1\) 的费用。

Matrix

给定 \(01\) 矩阵 \(A\)，构造矩阵 \(B\)，使得 \(A\circ B\) 每行和为 \(u_i\)，每列和为 \(v_i\)。

• 对于流网络中的点 \(v\)，其流量守恒

  \[\sum_{(i,v)\in E}f_{(i,v)}=\sum_{(v,j)\in E}f_{(v,j)} \]

  我们可以用这个等式来表示题目中的条件。

• 此题要求 \(\sum_{j}B_{ij}=u_i\) 和 \(\sum_{i}B_{ij}=v_j\)，根据等式我们构造出图：

  二分图，左边 \(n\) 个点，右边 \(m\) 个点；源点向左边点 \(i\) 连边 \(u_i\)，右边点向汇点 \(j\) 连边 \(v_j\)；\(A_{ij}=1\) 则左侧 \(i\) 向右侧 \(j\) 连 \(+\infty\) 的边。

一流对多流（志愿者招募）

若干区间，每个区间有代价。每个点都要求被覆盖一定的次数。求最小代价。

• 一流对多流，不能二（三）分图建图。
• 覆盖次数和最小代价两个限制，考虑费用流。流量限制次数，费用求代价。
• 令一个区间为 \(l\to r+1\)，流量为 \(1\)，费用为代价。
• 我们强制满流限制次数，即 \(i\to i+1\)，流量为 \(+\infty-a_i\)，\(a_i\) 表示要被覆盖次数。
• 此时最小费用为最小代价。

区间覆盖

若干区间，每个区间有收益，每个点被覆盖最多 \(k\) 次，求最大收益。

• 一流对多流，不能二（三）分图建图。
• 覆盖次数和最大收益两个限制，考虑费用流。流量限制次数，费用求收益。
• 选中的区间可以分成若干组，满足每组中的区间互不相交。
• 源点流出 \(k\) 的流量，强制满流，每个流量表示一组。则 \(l\to r+1\) 建边，流量为 \(1\)，费用为收益；\(i\to i+1\)，流量为 \(k\)。