A. 蜥蜴
次数的限制可以用拆点解决，然后直接连边即可。
B. OPTM - Optimal Marks
把二进制位拆开，套用最小割模型即可。
C. Hard Life
二分答案 \(x\)，然后对于每条边建立一个权值为 \(1\) 的点，点的权值设为 \(-x\)，边向其端点连边，然后跑最大权闭合子图即可。
D. Destroying the Graph
建立一张 \(2n\) 个点的图，表示每个点的两种操作。对于每条边，把消除它所需的两个点之间连边，那么答案就是二分图的带权最小点覆盖。
关于如何求二分图的带权最小点覆盖：考虑最小割模型。对于左侧的点 \(u\)，钦定它在源点侧代表不选、在汇点侧表示选；对于右侧的点 \(v\)，钦定它在源点侧代表选、在汇点侧代表不选。这样如果边 \((u, v)\) 存在，我们连一条 \(u \to v\)，流量为 \(\infty\) 的边就能规避二者都不选的情况了。
E. Exca 王者之剑
可以发现一个方案合法当且仅当方案中没有相邻的数同时被选中，于是问题等价于求二分图的带权最大独立集，方法同上。
F. order
最大权闭合子图，把任务向仪器连边的流量从 \(\infty\) 改为 \(b\) 即可。
G. 最大获利
最大权闭合子图。
H. 植物大战僵尸
最大权闭合子图。因为存在先后顺序所以需要在反图上拓扑排序确定那些点是可达的。
I. 剪刀石头布
发现对于 \(\forall A, B, C\)，若他们不满足条件，则肯定存在一个人胜过其他两个人，不妨设为 \(A\)，我们就枚举 \(A\)，然后用 \(\binom{n}{2}\) 减去最小的不合法数量即可。
那么我们首先可以建出模来：对于每一个没有进行的比赛建立一个点 \(M_{i, j}\)，对于每个人建立一个点 \(A_i\)，从 \(S\) 向 \(A_i\) 连边，容量为 \(n\)；从 \(A_i, A_j\) 向 \(M_{i, j}\) 连边，容量为 \(1\)；从 \(M_{i, j}\) 向 \(T\) 连边，容量为 \(1\)。这样最大流就是一种可行方案了。
若 \(A\) 胜了 \(m\) 场，那么就对应地有 \(\binom{m}{2}\) 组人不符合。我们可以考虑加上费用：假设当前 \(A_i\) 已经赢了 \(m\) 场比赛，那我们从 \(S\) 向 \(A_i\) 连容量为 \(1\)、费用为 \(m, m + 1, \cdots, n - 1\) 的边即可，这样每加一条就符合要求了。
给出方案的话可以考虑枚举每条边有没有流量。
J. 志愿者招募
我们考虑如下的一种建模思路：建立源点 \(s\)、汇点 \(t\) 和 \(n + 1\) 个结点表示每天，然后对所有 \(i \in [0, n]\) 连一条 \(i \to i + 1\)、容量为 \(\infty - a_i\)、费用为 \(0\) 的边；对于第 \(i\) 种志愿者，连一条 \(s_i \to t_i + 1\)、容量为 \(\infty\)、费用为 \(c_i\) 的边。这样的话如果存在合法答案最大流必定是 \(\infty\)，一条代表志愿者的边如果跨过若干个点就代表这个点连向下一个点的边的流量可以减少 \(1\)，而这条边的流量是 \(\infty - a_i\)，所以跨过这条边的志愿者边个数肯定有至少 \(a_i\) 个，这就满足了题意。
K. Chips Challenge
以为每一行 / 列的 \(a, b\) 是不同的，自闭了很久
不难想到钦定每行 / 列放的芯片数量上界，在此基础上肯定是放得越多越好。
看到网格容易想到二分图，问题是如何保证第一个条件。我们可以钦定所有芯片都放，然后每行 / 每列去掉相等数量的芯片即可，然后这个数量有一个下界，并且去掉的费用为 \(1\)。于是不难想到如下建图方式：
- 连 \(s \to i\)，流量为第 \(i\) 行可放置芯片 / 必须放置芯片的数量之和，费用为 \(0\)；\(j + n \to t\) 类似。
- 连 \(i \to i + n\)，流量为钦定的最大值、费用为 \(0\) 的边；
- 连 \(i \to j + n\)，流量为 \(1\)、费用为 \(1\) 的边，要求 \((i, j)\) 是可放置芯片的格子。
那么跑最小费用最大流，最大流为可放置芯片 / 必须放置芯片的数量之和则合法，此时最大放置数量为最大流与最小费用之差。
这个做法的精妙之处在于它用最大流保证行列数量相等的同时用最小费用求出了放置芯片数量的最大值。
L. 美食节
很厉害的题啊！
首先，有一个比较显然的费用流：我们把每位厨师 \(i\) 拆成 \(p\) 个点，\((i, j)\) 表示第 \(i\) 个厨师做的第 \(j\) 道菜。我们再对 \(n\) 种菜建立 \(n\) 个点，进行如下连边：
- \(s \to i\)，流量为 \(p_i\)、费用为 \(0\)；
- \(i \to (j, k)\)，流量为 \(1\)、费用为 \(k \times t_{j, i}\)；
- \((j, k) \to t\)，流量为 \(1\)、费用为 \(0\)。
然后我们发现这样连边可以是可以，但是连的边太多了！所有厨师一共才做 \(p\) 道菜，所以很多的 \((j, k)\) 肯定是无用的。注意到 \((i, k + 1)\) 有流量必然在 \((i, k)\) 有流量之后，所以我们可以在网络流 dfs 的过程中打上标记，当 \((i, k)\) 有流量之后再把 \((i, k + 1)\) 和连接其的边加入网络，这样我们就把连边数降到 \(\mathcal{O}(np)\) 级别了！
M. 文理分科
我们不妨考虑更普遍的问题：有两个集合 \(A\) 和 \(B\) 和 \(n\) 个有标号物品，要把所有物品放到两个集合内。把物品 \(i\) 放到集合 \(A\) 或 \(B\) 内分别可以获得 \(a_i, b_i\) 的收益。特别地，给定 \(m\) 个集合 \(S_1, \cdots, S_m\)，若 \(S_i\) 中的物品都在 \(A\) 或 \(B\) 内则分别可以获得 \(c_i, d_i\) 的额外收益。求收益最大值。
考虑最小割模型。我们发现一个问题，那就是：一个集合的物品分到两个集合之内时额外收益是不一样的。所以我们不妨把表示集合的点拆为两个点，即表示都在 \(A\) 里的点和表示都在 \(B\) 里的点，这样建图就比较显然了。
N. 最小割
不确定源汇点 / 多次查询最小割的题目可以往最小割树这方面想。
最小割树的构建：在当前点集中钦定两个不同的点 \(s, t\) 作为源汇跑最小割，然后在 \(s, t\) 之间连一条权值为最小割的边，然后往割的两边递归下去。注意我们递归时缩小的只是可以被钦定为源汇点的点集，而不是网络的点集。
那么这样构建出来的最小割树有什么性质呢？我们不妨考虑树上的一条路径，比如 \(u \to x_1 \to x_2 \to v\)，那么我们要求 \(u, v\) 之间的最小割，就可以分类讨论：
- 若最小割中 \(u\) 和 \(x_1\) 在同一部分中，则答案就是 \((u, x_1)\) 的权值；
- 否则，若最小割中 \(u\) 和 \(x_2\) 在同一部分中，则答案就是 \((x_1, x_2)\) 的权值；
- 否则，\(x_2\) 和 \(v\) 在同一部分中，答案就是 \((x_2, v)\) 的权值。
不难看出，\(u, v\) 之间的最小割就是其在树上路径权值的最小值。
预处理的复杂度是 \(\mathcal{O}(n^3m)\)，直接 \(\mathcal{O}(n^2 \log n) - \mathcal{O}(\log n)\) 地回答询问即可。
O. 星际战争
二分然后跑最大流即可。
因为本题精度要求并不高，把 \(a\) 乘上 \(10^4\) 就可以避免使用浮点数。
P. 切糕
切的这一刀把切糕分成了两半，我们钦定两半是 \([1, f(x, y)]\) 和 \((f(x, y), R]\) 不难想到使用最小割。
第二个限制如何刻画呢？不妨设 \(f(x, y) + D < f(x + 1, y)\)，这时考虑 \((x, y, f(x, y) + 1)\) 和 \((x + 1, y, f(x + 1, y))\) 这两个点，它们的高度之差 \(\ge D\)，而前者在上半部分、后者在下半部分。容易发现方案不合法等价于出现这种情况，所以在所有在相邻纵轴并且高度差 \(\ge D\) 的点对之间连权值为 \(\infty\) 的边然后跑最小割即可。
Q. 循环格
合法等价于每个点的入度和出度都是 \(1\)，于是枚举箭头的方向，跑二分图最大权匹配即可。
标签：费用,17,连边,网络,流量,最小,infty,权值 From： https://www.cnblogs.com/Scintilla/p/16717468.html