网络流 24 题题解

网络流24题小结

我才不会告诉你这是以前写的呢。

$1.$飞行员配对方案问题

题目

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员,其中1 名是英国飞行员,另1名是外籍飞行员。在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况,编程找出一个最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。

无解输出’No Solution!’

题解

本题没有无解情况
非常水的网络流入门题。
肯定是二分图(将飞行员按国籍分为两边)
直接建图,外籍放左边,英国放右边,S向左边所有点连边流量1,T向右边所有点连边流量1.
左边向右边按照题中给出关系连边流量INF.
最后答案为最大流.
两个飞行员之间可配对当且仅当连边的反边有流量.

$2.$太空飞行计划问题

题目

$W$ 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $E={E_1,E_2,…,E_m}$ ,和进行这些实验需要使用的全部仪器的集合 $I={I_1,I_2,…I_n}$。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subset I$。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。$W$ 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

题解

感觉这题其实还挺神的。
模型为最大权闭合子图,可以使用最小割解决。
将实验放到左边 $X$ 集合,器材放到右边 $Y$ 集合。
$S$ 向 $X$ 集合中的点连边容量为 $p_i$ 即收入, $Y$ 集合中的点向$T$连边容量为 $c_i$ 即费用,设 $Total=\sum_{i=1}^{n} p_i$ , $Cut$ 为求出的最小割(即最大流),那么答案为 $Total-Cut$,对应的解是最小割中的点,即增广完之后仍然可以从 $S$ 点到达的点。
接下来证明一下正确性,设集合 $A$ 为所有实验,集合 $B$ 为所有仪器,定义一个割划分出的 $S$ 集合为一个解。
那么割集的容量之和就是(未被选的 $A$ 集合中的顶点的权值 $+$ 被选的 $B$ 集合中的顶点的权值),记为 $Cut$。
$A$ 集合中所有顶点的权值之和记为 $Total$,那么 $Total – Cut$ 就是(被选的$A$集合中的顶点的权值 $-$ 被选的$B$集合中的顶点的权值),即为我们的目标函数,记为 $A$。
要想最大化目标函数 $A$,就要尽可能使 $Cut$ 小,$Total$ 是固定值,所以目标函数A取得最大值的时候,$Cut$最小,即为最小割。

$3.$最小路径覆盖问题

题目

给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上,则称 $P$是 $G$ 的一个路径覆盖。$P$ 中路径可以从$V$ 的任何一个顶点开始,长度也是任意的,特别地,可以为0。$G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。提示:设 $V={1,2,…. ,n}$,构造网络 $G1=(V1,E1)$ 如下:

题解

直接按照提示中的去做,将每个点 $i$ 拆成 $x[i]$ 放左边, $y[i]$ 放右边。
$S$ 先向左边集合连边,右边向 $T$ 连边,若原图中存在一条边 $(u,v)$,则建一条边 $(x[u], y[v])$, 所有边流量为 $1$,然后跑最大流出来二分图最大匹配数,点数减最大匹配数就是最少路径条数,如何输出也很简单,直接按照匹配边走就行。
正确性显然,可以自己想一下。

$4.$魔术球问题

题目

假设有n根柱子,现要按下述规则在这 $n$根柱子中依次放入编号为 $1,2,3,…$ 的球。

  • 每次只能在某根柱子的最上面放球。
  • 在同一根柱子中,任何 $2$个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 $n$ 根柱子上最多能放多少个球。例如,在 $4$ 根柱子上最多可放 $11$ 个球。

编程任务:

对于给定的 $n$ ,计算在 $n$ 根柱子上最多能放多少个球。

题解

这题需要用到上一题的解法。
首先考虑如果我们已经确定了球的个数,如何确定最少需要多少个柱子才能将他们全部放下,这个可以看成一个最小路径覆盖问题,我们对于每一个编号为 $i$ 的球,找到所有编号为 $j$ , $(j < i)$ 的球时两个球编号和为完全平方数,此时在图中由 $j$ 向 $i$ 连一条有向边。
显然当所有边连完后这个图一定为有向无环图,那么一个柱子上面放的所有球从下到上肯定是图中的一条路径,所以可以看成最小路径覆盖。
那么可以考虑枚举球的个数(或者你可能想二分),然后求最小路径覆盖数,覆盖数是随着球的个数增加而单调不递减的。
但是我们不能使用二分而应该使用枚举来做,因为如果二分的话每次二分都需要重新建图一遍,但是枚举每次加一个球只需要将连向它的边加进去然后继续在残量网络上跑就行了,复杂度会优于二分。
那么应该如何求出答案。
当我们的最小覆盖数(设为 $f$)第一次大于 $n$ 时,那么最多可以放的小球数为 $f-1$,然后按照路径打印答案即可。

$5.$圆桌问题

题目

假设有来自 $m$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i (i =1,2,……,m)$ 。

会议餐厅共有 $n$ 张餐桌,每张餐桌可容纳 $c_i (i =1,2,……,n)$ 个代表就餐。

为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法,给出满足要求的代表就餐方案。

对于给定的代表数和餐桌数以及餐桌容量,编程给出满足要求的代表就餐方案。

题解

将代表放在左边,餐桌放在右边。
考虑建模。
每个单位最多有 $r_i$ 个人可以就餐,那么从 $S$ 到点 $i$ 的流量最多为 $r_i$.
同样的道理右边集合中点 $j$ 到 $T$ 流量为 $c_i$.
由于一个餐桌中一个单位最多只能由一个代表,那么左边集合与右边集合中流量最多为 $1$.
那么我们跑最大流,然后如果流量<n,那么肯定不满足方案数,输出 $0$,不然的话有解,每个单位输出流量跑满的边所指向的右边集合中的点就行了。

$6.$最长不下降子序列问题

题目

给定正整数序列x1,…,xn 。
(1)计算其最长不下降子序列的长度s。
(2)计算从给定的序列中最多可取出多少个长度为s的不下降子序列。
(3)如果允许在取出的序列中多次使用x1和xn,则从给定序列中最多可取出多少个长度为s的不下降子序列。
设计有效算法完成(1)(2)(3)提出的计算任务。

题解

第一问

可以直接用 $O(n^2)$ 的 $DP$ 来做。
设 $f[i]$ 表示以 $i$ 位置为结尾的最长不下降子序列。
然后转移很简单。
第一问的答案为 $max{f[i]}$,设为 $K$。

第二问

使用网络流解决,使用一种分层图的思想进行状态转移。
将每一个点 $u$ 分成左右的两个点 $u1, u2$,然后由 $u1$向 $u2$ 连一条容量为 $1$的边,这是为了保证每一个点最多只能使用一次,对于所有满足 $f[i] = 1$ 的位置 $i$, 由 $S$ 点向 $i1$ 连边,对于所有满足 $f[i] = K$ 的位置 $i$,由 $i2$ 向 $T$ 连一条容量为 $1$ 的边,此时到了进行模拟转移的时候,对于一个位置 $i$,找到所有位置 $j$,满足 $j < i$ 而且 $a[j] <= a[i]$ 而且 $f[i] = f[j] + 1$ ,其实就是 $dp$ 中状态转移的条件。
然后由 $j2$ 向 $i1$ 连一条容量为 $1$ 的边。
跑出来最大流就是答案。

第三问

由于 $x_1, x_n$ 可以使用多次,那么将 $S$与 $1_1$之间的边容量改为 $inf$, $1_1$与 $1_2$ 之间的边容量也改为 $inf$,如果 $f[N]=K$ 的话,就将 $N_1$和 $N_2$之间的边容量改为 $inf$, $N_2$ 和 $T$ 之间的边的容量改为 $inf$, 此时跑出的最大流为第三问答案。

$7.$试题库问题

题目

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。
对于给定的组卷要求,计算满足要求的组卷方案。

题解

题目放 $X$ 集合,类型放 $Y$ 集合。
$S$ 向所有 $X$ 集合中的点连边容量为 $1$, $X$ 集合中的点分别向 $Y$ 集合中对应的类型的点连边容量为 $1$, $Y$ 集合中的点 $i$ 向 $T$ 连边容量为 $a[i]$。
跑出最大流若其不等于所有 $a[i]$ 之和(即 $m$),则无解。
不然的话就是有解的,直接根据流量判断就行了。

$9.$方格取数问题

题目

在一个有 $m\times n$ 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。

题解

这个可能方格图问题的某种解决套路吧,就是按照坐标黑白染色,建出二分图。
首先按照坐标之和为奇或偶进行黑白染色,将同种类型的放到一个集合中,然后会形成两个集合 $X, Y$,由 $S$ 点向 $X$ 集合中的点连容量为原图中权值的边, $Y$ 集合向 $T$ 类似的连边,由于不能同时选有相邻边的点,那么 $X$ 集合中的点向 $Y$ 集合中的与其有相邻边的点连边为 $inf$,根据建图方法肯定会是有相邻边的两点不在同一集合中。
此时跑出最大流,用所有格子的权值和减去最大流就是结果。

正确性

因为这样跑出来的最大流就是二分图的最小割,又由于中间的连边容量为无限大,所以肯定不会被割到,那么对一个格子(设它在二分图中属于 $X$ 集合),要么将他与 $S$ 之间的边割掉(这就相当于在原图中没有取这个格子),要么将其连向 $Y$ 中的所有点之间的连边割掉(这就相当于在原图中取了这个格子但是美取相邻的),由于是最小割,而且过程完全满足题中规定的条件,所以最小割就是不取的格子最小权值和。

$10.$餐巾计划问题

题目

一个餐厅在相继的 $N$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾($ i=1,2,…,N$)。餐厅可以购买新的餐巾,每块餐巾的费用为 $p$ 分;或者把旧餐巾送到快洗部,洗一块需 $m$ 天,其费用为 $f$ 分;或者送到慢洗部,洗一块需 $n$ 天($n>m$),其费用为 s 分($s<f$)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $N$ 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

题解

这题看到有位博主的总结写的不错,就直接贴上来了。
这个问题的主要约束条件是每天的餐巾够用,而餐巾的来源可能是最新购买,也可能是前几天送洗,今天刚刚洗好的餐巾。
每天用完的餐巾可以选择送到快洗部或慢洗部,或者留到下一天再处理。
在每一天的餐巾需求为 $r_i$ 的情况下,如果满足,必定余下 $r_i$ 个餐巾可以任意处置,所以我们新增流而不是将已经用的流流回。
把每天分为二分图两个集合中的顶点 $X_i$,$Y_i$,建立附加源 $s$ 汇 $t$。

从 $s$ 向每个 $X_i$ 连一条容量为 $r_i$,费用为 $0$ 的有向边。表示每天用完的餐巾
从每个 $Y_i$ 向 $t$ 连一条容量为 $r_i$,费用为 $0$ 的有向边。表示每天必须满足的需求
从 $s$ 向每个 $Y_i$ 连一条容量为 $\infty$,费用为 $p$ 的有向边。表示购买餐巾。
从每个 $X_i$ 向 $X_i+1(i+1\le N)$ 连一条容量为 $\infty$,费用为 $0$ 的有向边。表示餐巾,是可以放着不洗存到下一天的。
从每个 $X_i$ 向 $Y_i+m(i+m\le N)$ 连一条容量为 $\infty$,费用为 $f$ 的有向边。表示快洗。
从每个 $X_i$ 向 $Y_i+n(i+n\le N)$ 连一条容量为 $\infty$,费用为 $s$ 的有向边。表示慢洗。
此图最小费用最大流即为答案。

总结:本题反映了分析一类问题的方法,分析问题的约束条件,分析问题的所有可能决策,从而有的放矢的建图。边,有时候意味着一种决策,我们利用网络流,来获得最优决策。新增流的手法也是很重要。

$11.$航空路线问题

题目

给定一张航空图,图中顶点代表城市,边代表 $2$ 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。
$(1)$ 从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。
$(2)$除起点城市外,任何城市只能访问 $1$ 次。
对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

题解

最长不相交路径模型。
可以将题目要求(即从点 $1$ 到点 $N$, 然后回来,而不经过重复点的路径)转换一下,变成两条从点 $1$ 到点 $N$ 的没有重复点的路径。

由于每个点只能使用一次,那么我们会非常 熟练 自然的想到可以拆点,由于只能用一次,那么对于每一个点 $u​$ ,将其拆成两个点 $u_1, u_2​$, $u_1​$ 放到 $X​$ 集合中, $u_2​$ 放到 $Y​$ 集合中,然后由 $u_1​$ 向 $u_2​$ 连边 $(1, 1)​$ (特别的, $1​$ 和 $N​$ 的容量为 $2​$ ),对于原图中的边 $(u, v)​$ ,在建图时由 $u_2​$ 向 $v_1​$ 连边 $(1, 0)​$ ,然后跑一遍最大费用最大流,如果点 $1_1​$ 向 $1_2​$ 的连边不是满流就无解,注意可能要特判一下 $1->N->1​$ 的这种图。

$12.$软件补丁问题

题目

T 公司发现其研制的一个软件中有 $n$ 个错误,随即为该软件发放了一批共 $m$ 个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。

换句话说,对于每一个补丁 i,都有 2 个与之相应的错误集合 $B1[i]$和 $B2[i]$,使得仅当软件包含 $B1[i]$ 中的所有错误,而不包含 $B2[i ]$中的任何错误时,才可以使用补丁 $i$。补丁 $i$ 将修复软件中的某些错误 $F1[i]$,而同时加入另一些错误 $F2[i]$。另外,每个补丁都耗费一定的时间。

试设计一个算法,利用 T 公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少。对于给定的 $n$ 个错误和 $m$ 个补丁程序,找到总耗时最少的软件修复方案。

题解

这题感觉不用网络流啊。
直接用状压就行了。
都不用怎么讲。
按照题目把这些集合用二进制状压,1表示满足,0表示不满足。
然后用状态暴力spfa转移。

$13.$星际转移问题

题目

由于人类对自然资源的消耗,人们意识到大约在 $2300$ 年之后,地球就不能再居住了。于是在月球上建立了新的绿地,以便在需要时移民。令人意想不到的是,$2177$ 年冬由于未知的原因,地球环境发生了连锁崩溃,人类必须在最短的时间内迁往月球。

现有 $n$ 个太空站位于地球与月球之间,且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人,而每艘太空船 $i$ 只可容纳 $H[i]$个人。每艘太空船将周期性地停靠一系列的太空站,例如:$(1,3,4)$ 表示该太空船将周期性地停靠太空站 $134134134…$。每一艘太空船从一个太空站驶往任一太空站耗时均为 $1$。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上,太空船全在初始站。试设计一个算法,找出让所有人尽快地全部转移到月球上的运输方案。

对于给定的太空船的信息,找到让所有人尽快地全部转移到月球上的运输方案。

无解时输出 $0$

题解

我觉得这题的解法挺神奇的,其实说白了就是个套路

首先如果地球到月球没有路径就是无解的,直接先特判掉。

然后发现似乎无法直接求出最快的天数,由于猜到天数比较少,所以可以考虑与之前的魔术球问题类似的方法求得答案,就是一个个枚举答案(不二分的原因在”魔术球问题”中已经有所提及)。

对每一个点 $u$ 的每一天 $i$ 拆成点 $u_i$ ,为了表示方便,将月球编号为 $N + 1$。

假设当前枚举到了第 $n$ 天,考虑如何对这一天继续加边。

  • 由$S$ 向 $0_n$ 连容量为 $inf$ 的边, 表示地球每天可以有无数的人移民。
  • 由 $(N+1)_n$向 $T$ 连容量为 $inf$ 的边,表示月球每天可以接受无数的人。
  • 对所有空间站 $i$ ,连边 $(i_{n-1}, i_n)$,容量为 $inf$,表示空间站可以让前一天的所有人今天继续留在这里。
  • 对所有飞船 $x$,设其前一天在的空间站为 $stat_1$, 这一天在 $stat_2$,那么连边 $(stat_{1_{n-1}}, stat_{2_n)}$,容量为$H[x]$ ,表示飞船在这天可以将$stat_1$中的人载最多$H[x]$到$stat_2$。

第一次使最大流不少于地球移民人数的那天为答案。

$14.$孤岛营救问题

题目

$1944$ 年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形,其南北方向被划分为 $N$ 行,东西方向被划分为 $M$ 列,于是整个迷宫被划分为 $N\times M$ 个单元。每一个单元的位置可用一个有序数对(单元的行号,单元的列号)来表示。南北或东西方向相邻的 $2$ 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙,并且所有的门被分成 $P$ 类,打开同一类的门的钥匙相同,不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角,即 $(N,M)$ 单元里,并已经昏迷。迷宫只有一个入口,在西北角。也就是说,麦克可以直接进入 $(1,1)$ 单元。另外,麦克从一个单元移动到另一个相邻单元的时间为 $1$ ,拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法,帮助麦克以最快的方式到达瑞恩所在单元,营救大兵瑞恩。

题解

就是状压然后暴力 $bfs$ ,非常水,唯一需要注意的是每个点可能有多个钥匙。

$15.$汽车加油问题

题目

给定一个 $N \times N$ 的方形网格,设其左上角为起点◎,坐标 $(1,1)$ , $X$ 轴向右为正, $Y$ 轴向下为正,每个方格边长为 $1$ ,如图所示。

img

一辆汽车从起点◎出发驶向右下角终点▲,其坐标为 $(N,N)$。

在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

  1. 汽车只能沿网格边行驶,装满油后能行驶 $K$ 条网格边。出发时汽车已装满油,在起点与终点处不设油库。
  2. 汽车经过一条网格边时,若其 $X$ 坐标或 $Y$ 坐标减小,则应付费用 $B$ ,否则免付费用。
  3. 汽车在行驶过程中遇油库则应加满油并付加油费用 $A$ 。
  4. 在需要时可在网格点处增设油库,并付增设油库费用 $C$ (不含加油费用 $A$ )。
  5. $N,K,A,B,C$均为正整数, 且满足约束: $2\leq N\leq 100,2 \leq K \leq 10$。

设计一个算法,求出汽车从起点出发到达终点所付的最小费用。

题解

其实非常水,其实不需要用到网络流。

由于一个点的移动也可以看成同时存在的油箱内油的变化,所以可以按照油箱内的油量来分层。

到达点 $i$ ,剩余油量为$l$时,将这个状态表示为一个点 $<i,l>$ ,它处在的层肯定就是第$l$ 层,然后加边的方法就贴一下 BYVoid的吧。

  1. 如果油箱不满 $(l < K)$ ,点$i$为油库点,从 $<i,l>$ 到 $<i,K>$ 建立一条权值为$A$的有向边。
  2. 如果油箱不满 $(l < K)$ ,点$i$不为油库点,从 $<i,l>$ 到 $<i,K>$ 建立一条权值为A+C的有向边。
  3. 如果油箱不为空, $i$ 不为油库点,每层 $l$ 从$<i,l>$到$<j,l-1>$建立一条权值为0的有向边,其中j为i的右边或下边相邻的一个顶点;从 $<i,l>$ 到 $<j,l-1>$ 建立一条权值为B的有向边,其中j为i的左边或上边相邻的一个顶点。
  4. 如果油箱不为空,$i$ 为油库点,从 $<i,K>$ 到 $<j,K-1>$ 建立一条权值为0的有向边,其中j为i的右边或下边相邻的一个顶点;从 $<i,K>$ 到 $<j,K-1>$ 建立一条权值为B的有向边,其中j为i的左边或上边相邻的一个顶点。

求最短路之后答案就是 $min{dis[<N,N,k>]|0\leq k \leq K}$

$16.$数字梯形问题

题目

给定一个由 $n$ 行数字组成的数字梯形如下图所示。

img

梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  1. 从梯形的顶至底的 $m$ 条路径互不相交;
  2. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交;
  3. 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

题解

题目很水,不用多说。

考虑对于那种不能相交的东西(比如节点,路径),考虑如何建图中表示出来,不能相交,说明只能走一次,那么就按照一贯套路,将他们拆成两个点,连边流量为$1$,可以相交的就连边无限大。

接下来是三种情况分别如何连边(都是有向的):

  1. 把一个点$u$拆成两个点$u_1,u_2$, $u_1$向$u_2$连边$(1,a[u])$,即流量$1$,费用(或者说是贡献)$a[u]$,若两个点之间由连边(由上向下面的两个点),就由$u_2$向$v_1$连边$(1,0)$,$S$向最上面一层$m$个点连边$(1,0)$,最下面一层点向$T$连边$(1,0)$。
  2. 只需要改部分边的容量,$u_1$与$u_2$之间的边容量改为$inf$,因为点可以多次经过,最下面一层的点$v_2$与$T$的连边改为$inf$

,原因一样。

  1. 所有边容量都改为$inf$,但是$S$到最上面一层点$u_1$容量为$1$,因为无论怎样最上面每个点最多且必须用一次。

跑最大费用最大流后最大费用就是结果。

$17.$运输问题

题目

W 公司有 $m$ 个仓库和 $n$ 个零售商店。第 $i$ 个仓库有 $a_i$ 单位的货物,第 $j$个零售商店需要 $b_j$ 个单位的货物。
货物供需平衡,即 $\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$。
从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用为 $c_{ij}$。
试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。
两行分别输出最小运输费用和最大运输费用。

题解

其实和上面那个问题差不多,仓库放左边,商店放右边,$S$ 向左边连 $(a[i], 0)$的边(前面为流量,后面为费用,后同),右边集合向 $T$ 连 $(b[j], 0)$的边。
第i个仓库向第j个商店连边 $(INF, c_{ij})$。
跑完一遍费用流后还要把费用取相反数来跑一遍,以求出最大花费。

$18.$分配问题

题目

有 $n$ 件工作要分配给 $n$ 个人做。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案,使产生的总效益最大。
一个人只能修一个工件。
两行分别输出最小总效益和最大总效益。

题解

最小费用最大流,人放左边,商品放右边,$S$ 向人连 $(1, 0)$的边,商品向 $T$ 连 $(1, 0)$ 的边,人向商品连 $(1,c[i][j])$ 的边,因为每个人只能修一个工件,所以流量最大为 $1$。
然后跑费用流。
好像可以用二分图最佳完美匹配的 $KM$ 算法做,到时候学一下去。

$19.$负载平衡问题

题目

G 公司有 $n$ 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。

题解

考虑费用流。
首先可以确定每个仓库货物量最后应该是多少。
肯定是平均数。
然后考虑建模。
建立 $S$, $T$,然后将仓库按照货量与平均值的关系,大于平均值的放右边,小于平均值的放左边。
由 $S$ 向左边的集合连边,流量 $a[i]-sum$, 费用为零,表示最多可从 $S$ 点获得这么多流量,或者说实际上是可以向外最多移动这么多自己原有的货物。
由右边的集合向 $T$ 连边,流量为 $sum-a[i]$,费用为零,意义和上面的差不多。
考虑左右边集合之间的连边,由题目意思,只能相邻之间的仓库之间运输,所以相邻的点之间连边,流量为 $INF$,费用为1。
然后跑费用流输出最小费用就行。

$20.$深海机器人问题

题目

深海资源考察探险队的潜艇将到达深海的海底进行科学考察。

潜艇内有多个深海机器人。潜艇到达深海海底后,深海机器人将离开潜艇向预定目标移动。

深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。

每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。

本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可以在同一时间占据同一位置。

用一个$P\times Q$网格表示深海机器人的可移动位置。西南角的坐标为$(0,0)$,东北角的坐标为$(Q,P)$。

img

给定每个深海机器人的出发位置和目标位置,以及每条网格边上生物标本的价值。

计算深海机器人的最优移动方案, 使深海机器人到达目的地后,采集到的生物标本的总价值最高。

题解

其实挺水,但是我发现两个问题。

  • 边的编号要从$2$开始,不然反边加不了,我总是忘。
  • 最大费用最大流最好还是边权取相反数然后最小费用最大流再反过来靠谱一点,我直接写在松弛操作中不对。

就简单的讲一下一个点$u$到另一个点$v$(假设$u$在$v$的西方或南方)之间有$val$权值,应该如何连边。

  1. 首先新建一个点$x$,连边由$u$向$x$连一条$(1,val)$,由$x$向$v$连一条$(1,0)$。
  2. 再新建一个点$y$,连边由$u$向$y$连一条$(inf,0)$,由$y$向$v$连一条$(inf,0)$。

为什么这么建就不用多说了。

最大费用即为结果。

$21.$最长k可重区间集问题

题目

给定实直线$L$上$n$个开区间组成的集合$I$,和一个正整数$k$,试设计一个算法,从开区
间集合$I$中选取出开区间集合$S\subset I$,使得在实直线$L$的任何一点$x$,$S$中包含点$x$的开区间
个数不超过$k$,且$\sum_{z\in S}|z|$达到最大。这样的集合$S$称为开区间集合$I$的最长$k$可重区间集。$\sum_{z\in S}|z|$称为最长$k$可重区间集的长度。

题解

问题可以看做是求K条权之和最大的不想交路径,每条路径为一些不相交的区间序列。

那么就与之前的数字梯形问题差不多了。

连边直接贴一下BYVoid的吧。我懒得写了

按左端点排序所有区间,把每个区间拆分看做两个顶点$i.a, i.b$,建立附加源$S$汇$T$,以及附加顶点$S’$。

1、连接$S$到$S’$一条容量为$K$,费用为$0$的有向边。
2、从$S’$到每个$i.a$连接一条容量为$1$,费用为$0$的有向边。
3、从每个$i.b$到$T$连接一条容量为$1$,费用为$0$的有向边。
4、从每个顶点$i.a$到$i.b$连接一条容量为$1$,费用为区间长度的有向边。
5、对于每个区间$i$,与它右边的不相交的所有区间$j$各连一条容量为$1$,费用为$0$的有向边。

求最大费用最大流,最大费用流值就是最长$k$可重区间集的长度。

还有一种复杂度更低($O(N)$)的方法

离散化所有区间的端点,把每个端点看做一个顶点,建立附加源$S$汇$T$。

1、从$S$到顶点$1$(最左边顶点)连接一条容量为$K$,费用为$0$的有向边。
2、从顶点$2N​$(最右边顶点)到$T​$连接一条容量为$K​$,费用为$0​$的有向边。
3、从顶点$i$到顶点$i+1(i+1\leq 2N)$,连接一条容量为无穷大,费用为$0$的有向边。
4、对于每个区间$[a,b]$,从$a$对应的顶点$i$到$b$对应的顶点$j$连接一条容量为$1$,费用为区间长度的有向边。

求最大费用最大流,最大费用流值就是最长$k$可重区间集的长度。

$22.$最长k可重线段集问题

题目

给定平面$x-O-y$上$n$个开线段组成的集合$I$,和一个正整数$k$。试设计一个算法,从开线段集合$I$中选取出开线段集合$S\subseteq I$,使得在$x$轴上的任何一点$p$,$S$中与直线$x=p$相交的开线段个数不超过$k$,且$\sum_{z\in S} |z|$达到最大。这样的集合$S$称为开线段集合$I$的最长$k$可重线段集。$\sum_{z\in S} |z|$称为最长$k$可重线段集的长度。

对于任何开线段$z$,设其断点坐标为$(x_0,y_0)$和$(x_1,y_1)$,则开线段$z$的长度$|z|$定义为:

$$|z|=\lfloor\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}\rfloor$$

对于给定的开线段集合$I$和正整数$k$,计算开线段集合$I$的最长$k$可重线段集的长度。

题解

其实和$21$题差不多。

$23.$火星探险问题

题目

火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。

用一个$P\times Q$网格表示登陆舱与传送器之间的位置。登陆舱的位置在$(X1,Y1)$处,传送器
的位置在$(X_P ,Y_Q)$处。

X 1,Y 1 X 2 , Y 1 X 3 , Y 1 … X P-1, Y 1 X P , Y 1

X 1,Y 2 X 2 , Y 2 X 3 , Y 2 … X P-1, Y 2 X P , Y 2

X 1, Y 3 X 2 , Y 3 X 3 ,Y 3 … X P-1, Y 3 X P , Y 3

… …

X 1 ,Y Q-1 X 2 , Y Q-1 X 3 , Y Q-1 … X P-1, Y Q-1 X P , Y Q-1

X 1,Y Q X 2 , Y Q X 3 , Y Q … X P-1, Y Q X P ,Y Q

给定每个位置的状态,计算探测车的最优移动方案,使到达传送器的探测车的数量最多,
而且探测车采集到的岩石标本的数量最多。

题解

和深海机器人十分相像,就不具体说方法了。

输出方法就是:

对于每个点向右边和下面搜索可以取的点,即该点和那个点之间的连边的反边有流量,然后就走过去,$dfs$的开始点都是$(1,1)$,只要$K$遍就行,注意走过一条边后要把反边流量$-1$.

$24.$骑士共存问题

题目

在一个 n*n个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入

img

对于给定的 n*n 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击。

题解

我才不会说我之前一直都没用当前弧优化这次被卡才用起来的。

按照套路,将图黑白染色,将白点放到$X$集合,黑点放到$Y$集合,我们知道可以相互攻击的两个点一定在不同的两个集合中,然后按照套路将问题转化成最小割解决。

连边方式:

  1. $S$向$X$集合中的没障碍的点连边容量为$1$。
  2. $Y$集合中的没障碍的点向$T$连边容量为$1$。
  3. 对于可以互相攻击到的两个点从一个点(假设他在$X$集合中)向另一个点(肯定在$Y$集合中)连边容量为$inf$。

所有点数减去有障碍的点数然后减去最大流就是结果。

正确性可以参考一下之前的然后稍作思考就知道了。

sys_con

高一 OIer,常规 / 竞赛都渣得不行

2 thoughts to “网络流 24 题题解”

发表评论

电子邮件地址不会被公开。 必填项已用*标注

65 + = 73