网络流相关题目

一些（许多）例题

这里收录一些思维难度较高，不易看出网络流的题。

P3973 [TJOI2015]线性代数

题意 : 给定一个 (n * n) 的矩阵 B 和一个 (1 * n) 的矩阵 C。求出一个 (1 * n) 的 (01) 矩阵 (A)，使得 (D=(A×B-C) × A^{T}) 最大，其中 (A^{T}) 为 (A) 的转置，输出 (D)。

for 30% , n <= 15
for 100% , n <= 500

如果觉得这是个线性代数题，那就只能得到 30pts。

注意到要求的是 01 矩阵，且有好多 (1 * xxx) 和 (xxx * 1)等类型的矩阵。因此我们试着摆脱矩阵的限制，直接用表达式来表示 D。（可以用 n = 3 的情况来模拟一下）

[D = sum_{i,j<=n}{b_{i, j} * a_i * a_j} - sum_{i=1}^{n}{c_i * a_i} ]

然后我们发现实际上就是关于 (a_i)，对于参数 (b) 和 (c) 的选择问题。

首先我们先假设先选择了所有的 (a_i)，那么我们就要付出 (sum{c_i}) 的代价。但是我们有时候可以进行反悔操作。即，我们可以选择放弃 (a_i, a_j)，来以 (b_{i, j}) 的代价来代替 (c_i, c_j) 的代价。

具体些，我们先把所有收益 (sum{b_{i,j}}) 拿上，然后考虑付出最少的代价。我们可以选择付出 (c_i + c_j) 的代价，也可以选择 (b_{i, j}) 的代价。

更具体地，我们用一堆节点来表示 (b_{i, j})，用一些节点来表示 (c_i)。当我们选择了 (b_{i, j}) 时，就不能再选择 (c_i, c_j)了；当我们选择 (c_i) 时，我们也不能选择 (b_{i, j})。

再具体些，我们将 (b_{i, j}) 与源点相连，将 (b_{i, j}) 与 (c_i, c_j) 相连，将 (c_i) 与汇点相连。 然后跑最小割（最大流）。割掉哪个就表示选哪个作为代价。 最后答案为 (sum{b_{i, j}} - maxflow)

将两个矛盾点强制选择其一，再考虑反悔来回避矛盾，是最小割问题的一种常见思想，类似的思想还应用于最大权闭合子图的最小割理解。类题可见 : P4307 [JSOI2009]球队收益 / 球队预算（其中还涉及到拆边思想）

P2046 [NOI2010]海拔

给一张双向网格图，点有点权，每条边有两个权值（双向）。对于每个边权，它对答案造成的贡献为 (val[e] * max(height[v] - height[u], 0))（其中这条边为 (u) -> (v)）。已知(height[1, 1]=0)，(height[n, n]=1)。其余点权可以自由控制，为实数。求全局最小代价。

如果左上角和右下角权值都为 0，那么显然全局最优解就是0（所有点权都为0）。

现在右下角为 0.我们考虑每一条左上到右下的路径，有下降显然是不优的（因为要对 0 取 max，所以两点权值相等和权值下降时一样的）。那么如果我们上升，每次上升 0.多，怎么样？反正总和为 1，我们不如直接找到最小边权，让它乘上个 1 不是更好？

对于整个网格来说，我们让它左上全为 0，右下全为 1，中间挑选几个升到 1 的小边权的边即可。即，挑选一些边，使得左上部分的点属于 (S)，右下部分的点属于 (T)。并且要求边权和最小。

因此，答案就是网格的最小割。可以用对偶图来优化。

(Code:)my record

P3980 [NOI2008]志愿者招募

(n) 天， (m) 类志愿者，每类志愿者可以从 (S_i) 工作到 (T_i)，一共花费 (c_i)。现要求第 (i) 天的志愿者数量不少于 (a_i)，求所需最小费用。

我也不知到大佬们是怎么想出来的（直接模拟题意？），见图方式大概是这样：

一共 (n + 1) 个点，其中 (i) 向 (i + 1) 连边，表示第 (i) 天，流量限制为 ([a_i, +∞])，费用为0.
对于每一类志愿者((a_i, b_i, c_i))，我们从 (b_i + 1) 点向 (a_i) 点连一条流量限制为 ([0, +∞])，费用为 (c_i)的边。大概就是说从 (a_i) 到 (b_i) 这些天（即图中的那些边）添加一种可循环流，其花费为 (c_i)，可供流动以达到“天”边的流量下届。
没有超级源点汇点，直接跑无源汇有上下界最小费用最大流。

这说明：我们有时候可以用边的流量下届来限制一些必须完成的条件，用环流来提供达到限制的可能，这样就不用建立超级源汇了。

题意 : n个国家从左到右排列， m 个人从左到右游历这 (n) 个国家。对于游历了 (P_1, P_2, ..., P_k) 国家((0 <= k <= n))的人，需要的飞机费用为 (fare_{P_1, P_2} + fare_{P_2, P_3} + ... + fare_{P_{k-1}, P_k})（(fare{i, j}) 已知）。现已知到达每个国家的人数 (V_i)，求最小总花费。

每个国家可以被当作开始的国家游历，也可以由一些人做飞机来游历。游历一个人就要答案加一。同时，一个国家被某个人游历完，这个人还可以坐飞机去其它国家。

到达每个国家的人数限制比较严格，必须是给定的某个数。但是以某个国家为初始国家的人数不确定，但是总人数是给出上界的（每个人可以一个国家也不游历）。

（边以 ((low, up, fare)) 的格式表示）
将国家拆成两个点；建立一个副源点 (S')；建立一个源点 (S)，并 (S') 向 (S) 连边((0, m, 0))，流量（总人数）限制在 0 到 (m) 之间，不花钱。
由源点 (S) 连向所有国家的第一个点边((0, inf, 0))，表示初始国家，不限制人数（确切地说，不在这里限制），不花钱；
所有国家的第二个点向汇点连边((0, inf, 0))，仅方便统计答案，不限流量，不花钱。
所有国家第一个点向第二个点连边 ((V_i, V_i, 0))，表示进行游历，流量（人数）严格为 (V_i)，不花钱。
每个国家的第二个点向其右边国家的第一个点连边 ((0, inf, fare_{i, j}))，表示游历完后可以坐飞机到达另一个国家（当然也可以不去，直接流向汇点),不限人数，但要交费。

最后跑有源汇有上下界最小费用可行流。

P2469 [SDOI2010]星际竞速

题意：

n个点，m条边的有向无环图。边有边权。点有点权。现要求找到若干条路径，将每个点遍历一次且仅一次，最小化：

[sum_{chain}(val[start~point] + sum_e{val[e])} ]

Solution

因为每个点都只被遍历了一次且仅一次，并且遍历到每个点都需要付出一定的代价。

具体来说，我们将答案拆分，拆成 (start~point) 对答案的贡献和路径上其它点对答案的贡献。

如果该点作为起点，那么需要花费该点点权的代价（①）；

如果该点作为链上其它点，那么需要花费上一个点连向这个点的边权这么多代价（②）。

还有一些限制：每个点入度出度必须为1（③），包括起点（从虚拟节点走过来）和终点（走向虚拟节点）。因为每个点都只能被遍历到一次，因此所有边的容量应该都为1。没了。

于是有如下建图方式：

将点 (x) 拆成出点 (x) 和入点 (x')。
(S) 向所有的 (x) 连边，所有的 (x') 向 (T) 连边，容量均为1，不花钱。（③）
从 (S) 向所有的 (x') 连边，容量为1，费用为点权。（①）
从 (x) 向所有能到达的 (y') 连边，容量为1，费用为边权。（②）

P3227 [HNOI2013]切糕

题意:

给一个点带权（非负）的长方体点阵，要求在每一数列中选择一个点，符合相邻数列所选择的点的高度差不超过 (d)，要求最大化选出的点的和。输出最大点权和。

(n, m, h <= 40)

题解：

题解

如果 (d >= h)，那么我们就可以肆无忌惮地选点，自然是选择每一列中的最小点。如果把每一列都串成串，那么就是选择每一列中的最小割点。

我们多建一层，然后把点权放在相邻层间的边上。

现在有了 (d) 的限制，也就是说，如果选择了某一列的第 (i) 层的点，那么相邻列的 (1, 2, 3, ..., i - d - 1) 层的点和第 (i + d + 1, ... h) 层的点都不能选了，那么我们就可以根据此限制，让选择不合法点对不能构成最小割（类似二元关系模型的某些思想）。可行的方法为：将某一列的第 (i) 层点连向相邻列的第 (i-d) 层点，这样如果我们选择了不合法点对，就不能构成最小割（没有完全割断）。

P4382 [八省联考2018]劈配

题意：

(n) 名选手已经填好志愿（选导师），且保证每个志愿最多选 (C) 位导师，每位导师被每位选手最多选择一次。若某志愿选择了多位导师，则将该选手加入到任意一位已选择的导师团队都能符合该选手的志愿。共 (m) 位导师，每位导师团队最多有 (b_i) 名选手，每位选手最终最多只能加入到一个团队中。

我们要求排名靠前的选手尽可能地实现其最高的志愿。

每位选手还有一个期望志愿，实现不低于该志愿都能够满足该选手的期望。

要求合法安排方案，输出最优情况下这 (n) 名选手的第几志愿被实现；同时输出每名选手至少需要提升几名才能达到其期望。（无解特判）

(n,m<=200,c<=10)

题解

~~用自己的思路做出来的第一道n省联考题~~

不得不说，这道题真的不是很难，况且暴力+特判+贪心就有60分。

题目明显提示二分图（网络流）。

题意明显证明网络流（最优情况 -> 最大流。每位选手只能选一个导师；每个导师团队最多容纳 (b_i) 个人 -> 限制流量。根据后面选手的选择情况，可能会对前面选手的选择进行微调 -> “退流”操作。200范围 -> 贪心不好搞 -> 网络流）

很自然想到选手与导师匹配。第一问就从前往后模拟题意:每次尝试选该选手的更高志愿（向导师连边），若可以增广，则保留边，记录答案；否则删边尝试下一个。每次增广大致 (O(n))，最多增广 (O(n)) 次。最终复杂度大致 (O(n^2))

第二问暴力枚举 (O(n^4))，二分模拟 (O(n^3logn))，但是估计跑不够。

实际上求第一问的时候顺便求一下每一位导师团队最早什么时候满员且无法通过调整使其多出来一点流量（最小割必须边）。每位选手的期望导师的“满流时间”最大值即可更新答案。复杂度 (O(n^2))。

题目大概可以出到500，因为极限情况复杂度是 (O(n^3)) 的（(n^2) 遍 (bfs))

由于这道题要支持删除最后加入的某些边，因此用(vector) 存图会更方便些。

弧优化：记录当前 (vector) 的下标。

反边：每一条边单独开一个存反边下标的数组。（反边的起点一定是正边的终点）

P4003 无限之环

如何看出网络流？

水管 -> 点；

水管的连接 -> 匹配；

不漏水 -> 跑满流；

最小旋转次数 -> 最小费用

如何支持旋转？

分类讨论。

首先拆点（上下左右中），模拟题意连初始的免费边，再讨论旋转后边的情况以及费用情况。

能否不拆点？

否

拆点后便于我们控制原来的某一方向的改变，从而做到有条不紊；如果不拆点，就没有方向的限制了，可能会把一个 (L) 型搞成 (|) 型，然后WA掉。

如何处理连接？

二分图匹配.

像这种网格题（甚至三位方块题），应该能迅速地想到拆出“行点”“列点”的模型（互斥）或者黑白染色后匹配的模型（匹配）。

注意右部图的连边全部是反过来的。

#6058. 百步穿杨

如何解决线路交叉问题?

首先根据套路，我们将每一条“路径”都自动给它一个收益10，然后再让每条“路径”放弃一些收益来保证合法，题目转化为最小割问题。

现在，我们要做的是，如果两条路径相交，那么我们需要视其为不合法情况，并且将其中一条路径在“相交点”之前拦下。如果我们能够构建一张图，能够沿着第一条路径从 (S) 以及路径起点走到 “相交点”，再沿着第二条路径向回走走到路径起点以及 (T)，路径上的边的权值设为在这里拦下的额外花费（放弃的收益），那么问题得解。

一种可行的建图方式：

百步穿杨