网络瘤 24 题做题寄录

前言

貌似并不知道要说什么(?)

网络流写麻了

 

 

(一)P3358 最长 $k$ 重区间集问题

题意:给定 $n$ 个左闭右开的区间,从这些区间中选取一些区间,使得数轴上没有任何一个点被超过 $k$ 个区间包含,并使得区间覆盖长度最大。

题意没给 $l,r$ 范围,先离散化。

先找流量和费用。首先有一个【每个区间只能选择一次】的隐性条件限制。可以想到将次数作为流量,显然长度就作为花费。

那么怎么表示选择一个区间呢?我们可以将区间左端点连向右端点,流量为 $1$,费用该区间的长度。

一点最多选 $k$ 次,那么我们对于数轴上每一个点 $i$ 连向 $i+1$,容量为 $k$,费用为 $0$。

跑一边最大费用最大流即可。

(二)P4014 分配问题

题意:$n$ 个工件分给 $n$ 个工人,第 $i$ 个人做第 $j$ 个工件的效益为 $c_{i,j}$,求问在一个零件只能匹配一个工人,并且一个工人只能加工一个零件的情况下,效益最大是多少。

显然有一个二分图的模型,把工人放到左边,零件放到右边。中间是若干边。

很套路的,建立一个虚拟源点 $s$,连向每一个工人,容量为 $1$,费用为 $0$,表示一个工人只能匹配一个,没有匹配零件所以没有费用。

同样,建立一个虚拟汇点 $t$,每一个零件连向汇点,容量为 $1$,费用为 $0$。

之后对于第 $i$ 个工人和第 $j$ 个零件连一条容量为 $1$,费用为 $c_{i,j}$ 的边,表示一个工人和一个零件只能匹配一次,获得的价值为 $c_{i,j}$。

要使效益最大,最后跑一边最大费用最大流。

(三)P2774 方格取数问题

题意:$m\times n$ 的方格,每个方格有一个数,选取若干的数,使得任意两个选取的数在方格中没有公共边,求最大和。

直接做不好做,考虑假设我们选取的了所有的数,那么现在我们要求最少删掉的代价。

这样就很像最小割了。

我们对于图黑白染色,若 $(i+j)\bmod 2=1$,则该点为黑,否则为白。

建立虚拟源点 $s$,和虚拟汇点 $t$。我们令 $s$ 连向每一个黑点,容量为点权。每一个白点连向 $t$,容量同样为点权。表示我们删去这个点需要的价值。

我们将每个黑点连向与它四联通的白点,容量为无限大。

根据最大流 = 最小割,跑一遍最大流就行了。

为什么这样做是对的,性感理解一下。但考虑一张 $s\to u\to u’\to t$ 的图,我们跑最大流肯定是在 $s\to u$ 和 $u’\to t$ 这两条边之间取的最小值,因为如果取了最大值就会超过另一条边的容量。这也就是求得删去的数的最小值。边权为 $\infty$ 表示这两个点见只能选择一个,因为最小割肯定不会割掉边权为 $\infty$ 的边。

最后有所有点的总和减去最小割即可。

(四)P4015 运输问题

题意:单位 $i$ 有 $a_i$ 单位的货物,商店 $j$ 有 $b_j$ 的货物需求量,保证 $\sum a_i=\sum b_j$。第 $i$ 个单位运到第 $j$ 个商店需要花费 $c_{i,j}$ 的代价,求最小和最大费用。

看出这是一个二分图模型,把单位放到左边,商店放到右边。

很显然是个费用流。货物量就是流量,代价就是费用。因为题目中保证 $\sum a_i=\sum b_j$,所以想到源点流出的流量等于汇点接受的流量。

建立虚拟源点 $s$ 和虚拟汇点 $t$,$s$ 连向每一个单位,容量为该单位的货物量,费用为 $0$。每一个商店连向 $t$,流量为该商店的需求量,费用为 $0$。

最后对于每一个单位连向每一个商店,容量无限大,费用就是那个代价。

最后跑一次最小费用最大流和一次最大费用最大流即可。

(五)P2762 太空飞行计划问题

题意:有 $m$ 个实验。每个实验只能进行一次,但会获得相应的奖金,有 $n$ 个仪器,每个实验都需要一定的仪器,每个仪器可以应用于多个实验,但需要一定的价值,问奖金与代价的差的最大值是多少?输出方案。

我们假设选择了所有实验,但所有的仪器先不选,然后找到一个花费最小的方案去掉若干个实验。

这就像最小割了。跟方格取数问题一样。

我们建立虚拟源点 $s$ 和虚拟汇点 $t$,然后 $s$ 连向每一个实验,流量为奖金,每一个零件连向 $t$,容量为花费。

求最小割,就相当于跑最大流。

怎么解释这件事情。考虑我们一开始求得奖金总和,假设我们割掉了某一个仪器,那么就相当于这个仪器不选,恰好减去他的奖金。如果割掉了某个零件,就相当于选了这个零件,同样花费了它的代价。

至于输出方案,有一个结论,在最后一次 $\text{Dinic}$ 中,被分到层上点都不会被割掉。

性感证明一下:我们在选择从 $s$ 到仪器的边中,最后一次肯定会选择满流的点,而那些没有满流的点都是被割掉的。然后会对那些满流的节点分层,最后只需判断一下一个点是否分了层即可。

(六)P2770 航空路线问题

题意:从西到东有 $n$ 个城市,$m$ 个航线,每个航线单向连接两个城市。求从最西的城市到最东的城市再回最西城市,除最西和最东城市每个城市只经过一次情况下,经过城市数最多,并输出方案。

首先可以得出一些性质:考虑来回一趟的旅程就相当于从起点到终点两趟,两次不经过相同的城市。【每一个城市只能遍历一次】的条件说明每一条航线也只能遍历一次。

【每一个城市只能经过一次】这一限制条件很套路,将每一个城市拆成两个点,一个入点 $u$ 和一个出点 $u’$,我们连从 $u$ 到 $u’$ 容量为 $1$ 的边,表示这个点只能经过一次,而题目又要使得经过城市数尽量多,所以可以看出是最大费用最大流的问题,我们让 $u$ 到 $u’$ 的费用为 $1$,表示经过了一个城市。

之后对于每一条航线,根据一开始推出的每条航线只能经过一次,我们对于每一条航线 $(x,y)$,从 $x’$ 到 $y$ 连一条容量为 $1$,费用为 $0$ 的边。

最后跑最大费用最大流即可。

输出方案仍然很简单,网络流有一个性质就是,流量为 $0$ 的边一定是被选上的。那么我们从起点开始 $dfs$,每一次找边权为 $0$ 的边暴搜下去。然后搜两次,第二次反着输出,因为是返程。

(七)P2754 星际转移问题

题意:有 $n$ 个太空站,容量无限,$m$ 艘飞船,每艘船有容量 $h_i$,第 $i$ 搜飞船会周期性的停靠太空站,$k$ 个人在地球 $0$,要使所有人都飞往月球,最快需要多少时间。

考虑按时间分层的 $\texttt{trick}$。

我们枚举答案 $T$,那么我们对于每一个船在 $T-1$ 时刻所到达的星球与 $T$ 时刻所到达的星球连一条容量为 $h_i$,表示最多装 $h_i$ 的人。

当然,上一个时刻的每一个空间的人都可以停留,那么我们将每一个星球上一个时刻和这一个时刻连一条容量为 $\infty$ 的边,表示这个空间站的容量是无限大的。

特殊的,我们建立虚拟源点 $s$ 和虚拟汇点 $t$,我们将 $s$ 连向地球,容量无限大,月球连向 $t$,容量也为无限大。

对于每一个时刻都跑最大流,直到最大流不小于 $k$ 为止,说明可以载够 $k$ 个人了。

判断无解考虑并查集即可。

(八)P3254 圆桌问题

题意:$m$ 个单位,第 $i$ 个单位派出了 $r_i$ 个代表。有 $n$ 个桌子,第 $i$ 个桌子可以容纳 $c_i$ 人,要求同一个单位的代表不能做相同桌子,求一个合法方案。

不难看出这也是一个二分图模型,把单位放在左边,桌子放在右边。

我们先建立虚拟源点 $s$,让 $s$ 连接每一个单位,容量为改单位的代表人数,表示一个单位的初始人数,我们想让这些人都不在同一个餐桌,那么就可以通过流量来起限制作用,我们将每一个单位向每一个餐桌连接一条流量为 $1$ 的边,表示该单位只能对该桌派出一个代表。而餐桌也是有名额限制的,我们将每一个餐桌向虚拟汇点 $t$ 连一条容量为 $c_i$ 的边。

如何判断无解,充要条件是源点的流出量必须等于汇点的接收量。

那么如何判断每一个人都坐在哪些位置呢?还是判断每一条边的流量是否为 $0$,即可找到每一个人坐到了哪一个餐桌。

(九)P1251 餐巾计划问题

题意:有 $n$ 天,每一天会需要 $r_i$ 个毛巾。可以直接购买新毛巾,或将现有毛巾送到慢洗部或快洗部花一定的钱洗若干天。毛巾用一天就会脏。求最小花费。

我们发现并没有很显然的二分图模型,但发现有【毛巾用一天就会脏】这一条件,提示我们按照【白天】和【黑夜】分层。

我们对于每一天构建两个点,一个黑天一个白天。我们将黑天放左边,白天放右边。

我们知道,每一天的 $r_i$ 个毛巾是必须要满足要求的,那么我们可以把毛巾需求量作为流量。而题目又要使花费最小,不难发现是一道最小费用最大流的问题。

我们建立虚拟源点 $s$,我们将 $s$ 向每一个黑天连容量为 $r_i$,费用为 $0$ 的边。表示获取这么多的脏毛巾。

同样,我们建立虚拟汇点 $t$,我们将每一个白天向 $t$ 连容量为 $r_i$,费用为 $0$ 的边,表示当天用了这些干净的毛巾。

现在考虑怎样将从源点获取的脏毛巾转变为干净的毛巾。

最直接的是买毛巾。直接从源点获取。向白天连一条容量无限大,费用为每块餐巾的费用。

之后就是快洗和慢洗的问题了,将当天晚上连向洗完那天的白天,容量为无限大,费用为快洗或慢洗的花费。

还有一个小坑,就是当天的脏毛巾可以拖到明天,或是更远几天再洗,那么我们将每一天晚上连向第二天晚上一个容量为无限大费用为 $0$ 的边。

跑一遍最小费用最大流即可。

(十)P2763 试题库问题

题意:有 $n$ 个试题,每个题有若干个 $\texttt{tag}$,要抽取 $m$ 个道题组成的试卷,类型 $i$ 的试题需要 $a_i$ 个。求一个合法的试卷组合。

这也有一个二分图模型,左边是试题,右边是类型。

由于一个试题只能用一次,那么我们从源点向每一个试题连一个容量为 $1$ 的边。

而当我们选择一个试题之后,就会获得一些 $\texttt{tag}$,那么我们将每一个试题向它的每一个类型连一条容量为 $1$ 的边,最后每一个类型向汇点 $t$ 连容量为 $a_i$ 的边。表示 $i$ 类型的题需要 $a_i$。

最后跑一遍最大流。

输出的方法还是一样,找流量为 $0$ 的边就行了。

(十一)P2766 最长不下降子序列问题

题意:给定长度为 $n$ 的数列,求:①最长不下降子序列的长度 $s$;②每一个元素只能使用一次的情况下,最多可以取出多少个长度为 $s$ 的不下降子序列;③若 $a_1$ 和 $a_n$ 可以使用多次,最多可以取出多少个长度为 $s$ 的不下降子序列。

第一问直接 dp,并记录最长不下降子序列的长度 $F$ 和 $dp_i$,表示以 $i$ 为结尾的最长不下降子序列的长度。

考虑二三问。

首先发现每个元素只能使用一次,那么套路的,我们对于每一个元素拆点,中间的流量为 $1$,表示只用一次。

然后枚举 $dp$ 值为 $1$ 的位置,这种位置只能放在开头,那么我们将 $s$ 向它连一条容量为 $1$ 的边。

同理,再枚举 $dp$ 值为 $F$ 的点,这种点只能放在结尾,所以我们将它连向 $t$,容量为 $1$。

然后考虑把 $s$ 和 $t$ 关联起来,很容易想到,$dp$ 值其实就相当于一个分层操作,对于两个点 $i,j$,如果 $a_i\ge a_j$ 且 $dp_i=dp_j+1$,那么说明 $j$ 可以转移到 $i$,我们将 $j$ 到 $i$ 连一条容量为 $1$ 的边。

跑一遍最大流就是第二问的答案。

第三问也很简单,我们将 $s$ 到 $1$ 和 $1$ 到它的拆出来的点的流量都改成无穷大。

但是只有在 $dp_n=F$ 的情况下我们才更改 $n$ 到 $n$ 对应的拆出来的点,和拆出来的点到 $t$ 的流量。这是一个小坑。

最大流即可。

(十二)P3355 骑士共存问题

题意:在 $n\times n$ 的棋盘上放置马,使得任意两个马不攻击,有 $m$ 个给定的位置不能放,求最多放几个马。

虽然不能说跟刚刚的方格取数问题一模一样,但也是很类似了。

同样假设取了所有点,然后最小化减少矛盾的马的数量就是最大化答案。

这样对原图黑白染色,然后跑最小割即可。

(十三)P4013 数字梯形问题

题意:给定一个数字梯形,从最顶端开始走 $m$ 条路径,每次朝左下或右下走,三问(一)路径不能相交(二)只能在节点处相交(三)可以在节点或边相交。

我们发现起点有 $m$ 个,是分散的,不如先建立 $s$ 连向第一行的每个数。然后最后一行的每一个点连向 $t$。容量 $1$,费用 $0$。

先考虑第一问,发现又有节点只能经过一次的限制。直接拆点,中间连容量为 $1$,费用为该节点的权的边。

然后每一个点的出点连向下面一行左边和右边的点,容量为 $1$,费用为 $0$。因为边也只能经过一次。

对于第二问,我们直接将每个点的入点和出点的容量改为 $\infty$,表示每个点可以经过无限次。有一个小坑就是最下面一行的每一个点连向 $t$ 的容量也都改为 $\infty$,因为某一条路径到达最下面的某一个点后,已经结束了,所以跟到终点的容量没有关系。

对于第三问,除了 $s$ 到第一行每一个点的边以外的所有边的容量都改为 $\infty$。

然后你就会发现一个特别恶心的事情,对于每一问都得重新建图。

(十四)P2764 最小路径覆盖问题

题意:给定一个 $\texttt{DAG}$,最少多少条简单路径能覆盖所有点。输出路径。

关于这道题有一个非常巧妙的解法。

首先发现答案的上限是 $n$,因为每一个点都可以被它直连的一条边覆盖,一共 $n$ 个点,所以答案最多是 $n$。

然后考虑合并边,每合并两条边答案就减少 $1$,所以考虑通过最大流来找出边的最大合并数。

这样就很好做了,对于每一个点拆点,然后 $s$ 连向每一个入点,容量 $1$,每一个出点连向 $t$,容量 $1$,之后对于每一条 $(x,y)$,连 $x$ 到 $y’$ 的一条容量为 $1$ 的边即可。表示合并了两个点。

最后跑一边最大流,答案就是 $n$ 减去最大流。

输出方案采用并查集维护起点,然后对于每一个起点顺着残余网络暴力 $dfs$ 即可。

(十五)P4009 汽车加油行驶问题

题意:给定 $n\times n$ 的方格,坐上 $(1,1)$ 为起点,右下 $(N,N)$ 为终点,$X$ 轴向右为正,$Y$ 轴向下为正,在若干个点上设置了油库可供加油,汽车只能沿着网格边走,遇到加油站必须加油,装满油后最多走 $k$ 条边,初始油量已满。汽车移动时若 $X$ 或 $Y$ 坐标减小,则需花费 $B$ 的费用。加油需要花 $A$ 的费用,可以在某一个没有加油站的点花 $C$ 的费用使油量变满。求最小费用。

这道题很显然是分层图最短路,所以考虑网络瘤。

显然费用流。

我们将图分为 $k+1$ 层,第 $0$ 层表示满油,第 $i$ 层表示用掉了 $i$ 个单位的油。第 $k$ 层就表示油被用光。

我们用三元组 $(x,y,z)$ 表示一个点 $(x,y)$ 的已用油量 $z$。

建立虚拟源点 $s$ 和虚拟汇点 $t$。

首先从 $s$ 到 $(1,1,0)$ 连一条流量 $1$,费用为 $0$ 的边,表示初始油量已满。对于每一个 $i$ 连从 $(n,n,i)$ 到 $t$ 的流量为 $1$,费用为 $0$ 的边,表示到达终点后车的可能的 $k+1$ 种状态。

之后考虑有加油站的点 $(i,j)$,汽车会被强制消费。所以 $(i,j,z)$ 连向 $(i,j,z+1)$ 流量 $1$,费用 $A$ 的边。然后枚举周围点,从状态 $0$ 到状态 $1$ 连边。注意如果横纵坐标减小应该额外花费 $b$。

然后对于普通点也是同理,只不过连周围点的时候要枚举当前点的状态。

特殊的,若当前点的状态是 $k$ 即油没了,连一条 $(i,j,k)$ 向 $(i,j,0)$ 流量 $1$ 费用 $a+c$ 的边。

(十六)深海机器人问题

题意:有一个 $P\times Q$ 的网格图,左下角为 $(0,0)$,右上角为 $(Q,P)$。有 $k$ 个机器人在不同出发地点,有若干目标地点,每个目标地点只能容纳 $r_i$ 个机器人,有些地方有生物标本,每个生物标本有价值,每个生物标本只能被第一个到达它的机器人取走,机器人只能向北或东走,若干机器人可以占据同一位置。求最高价值。

很显然的最大费用最大流了。每个点分别向右边的点连两条边,一条容量 $1$,费用为该点价值,一条容量无限,费用 $0$,表示取走一次再不能取。向上同理。

最后把起点和 $s$ 连起来,终点和 $t$ 连起来,容量为机器人数目,费用为 $0$。

最后跑最大费用最大流即可。

(十七)最长 $k$ 重线段集问题

题意:给定平面直角坐标系 $n$ 个线段,从这些区间中选取一些线段,使得对于任意一点 $p$ 没有任何一条直线 $x=p$ 与超过 $k$ 个线段,并使得线段长度最大值。

其实是最长 $k$ 重区间集问题的升级版,把区间放到直角坐标系上了。

那么一个很直接的想法就产生了,直接把线段投影到 $x$ 轴上!这样就和最长 $k$ 重区间集问题一模一样了。

但是很遗憾,这个想法是错误的,反例也很简单,假设说两条线段在一条是平行于 $y$ 轴的,投影之后就变成一个点了,导致错误。

那么不难想到把线段的长度都扩大一倍,即将线段 $i$ 的左右端点 $x_i,y_i$ 都扩大一倍变成 $(2x_i,2y_i)$。

而对于一个左右端点相同的区间,可以将它更改成 $(2x_i,2x_i+1)$。其它节点也都需要更改成 $(2x_i+1,2y_i)$ 的形式。

(十八)魔术球问题

题意:$n$ 个柱子,依次放入无限个球,球从 $1$ 开始编号。每次只能在某根柱子最上面放球,并且在同一个柱子中,任何两个相邻球的编号之和为完全平方数。输出方案。

我们考虑当前放置的球 $i$,它有两种可能,一是放到某一根已经有魔术球的柱子上,二是自己放到一个新的桌子上。

我们将球分裂,一个入点,一个出点。

首先我们可以将 $s$ 连向入点,容量为 $1$,表示放到一个新的柱子上。出点连向 $t$,容量也为 $1$,这里很重要,表示我们成功放上了一个球

然后枚举可以与它构成完全平方数的数 $x$,将 $x$ 的入点连向它的出点,容量为 $1$,表示一个匹配关系。

跑最大流,直到最大流大于 $n$,说明所需的柱子量超过了 $n$,那么停止。

输出方案找流量为 $0$ 的边,暴力 $\texttt{dfs}$ 即可。

还有亿点细节。

(十九)火星探险问题

题意:给定一张网格图,每个点有三种状态,平坦,障碍或岩石标本。有 $n$ 个探测车在移动中须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。求最多获得的岩石标本数。要求打印移动方向。

一道非常板的网络流了。显然车的数量为流量,石头数为费用。

令 $s$ 向 $(1,1)$ 连流量 $n$ 费用 $0$ 的边,表示初始有 $n$ 辆车。$(n,n)$ 连向 $t$,容量 $\infty$,花费 $0$,表示结束任务。

既然涉及到每个石头只能取一次,那么显然是可以拆点的,拆为 $a_{i,j}$ 和 $b_{i,j}$。

如果 $(i,j)$ 处有石头,那么可以连 $(a_{i,j})$ 到 $b_{i,j}$ 的流量 $1$,费用 $1$ 的边,表示只能有一个车取一个石头。石头也可以被取走,连另连一条流量 $\infty$ 费用 $0$ 的边。

另外还有相邻的点连线,每次都是出点连入点,流量 $\infty$ 然后费用 $0$。

最后就是最大费用最大流。

输出路径还是暴力 $\text{dfs}$。

 

$$\texttt{The End.by UF}$$

 1 total views,  1 views today

页面下部广告