网络流24题刷刷刷

网络流24题刷刷刷

魔术球问题

题意:

假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 123的球

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

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

做法

二分答案,对于每个枚举的答案建图,将可以组合成为平方数的两个点连边,问题转化为求解该dag的最小路径覆盖问题,具体做法就是将每个点拆成两个点,一旦有形如u\rightarrow v的边,则在二分图中将左部图u对应的点与右部图v对应的点相连,则最小不相交路径覆盖=点数-最大匹配数

扩展:DAG的最小相交路径覆盖

用floyd求原图的传递闭包,如果对于点u,vu可以到达v,那么就将二分图中左部图的u点与右部图的v点相连,然后问题即转化为求解最小无相交路径覆盖问题

最长不下降子序列问题

题意:

给定正整数序列 x_1,\cdots,x_n。(n\le500)

  1. 计算其最长不下降子序列的长度 s
  2. 如果每个元素只允许使用一次,计算从给定的序列中最多可取出多少个长度为 s 的不下降子序列。
  3. 如果允许在取出的序列中多次使用 x_1x_n(其他元素仍然只允许使用一次),则从给定序列中最多可取出多少个不同的长度为 s 的不下降子序列。

做法:

第一问考虑直接暴力dp,得到f数组

第二问很容易考虑一个流代表一条LIS,由于有限制每个元素只能被允许使用一次,所以我们考虑拆点,将入点与出点连一条流量为1的边,这样通过这个unit的流量就被限制为1了。然后将原点与二分图左部中f=1的点相连,作为LIS开始的起点,将二分图右部中f=ans的点相连,作为LIS结束的终点。

第三问由于可以无限次使用x_1,x_n 意思就是经过x_1,x_n的流量无限制。对应于二分图中即为源点流向左部图1的流量以及左部图1流向右部图1的流量都为正无穷,左部图n流向右部图n的流量也是正无穷,如果右部图n连向了汇点,则该边流量也是无穷

总结:

可以用拆点的方法应对过点流量的限制

航空路线问题

题意:

给定一张航空图,图中顶点代表城市,边代表两城市间的直通航线,并且不存在任何两个城市在同一条经线上。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

  1. 从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。
  2. 除起点城市外,任何城市只能访问一次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

做法:

首先问题可以转化为求两条首尾相同,中间节点均不相同的路径,且路径经过的点最多。

由这题和上一题有一点点相似,都是要求任何点只能够经过一次,所以很容易想到拆点。如此建图之后,我们并不能满足路径所经过的点最多。于是我们将左部图往右部图的边设置费用为1,于是求最大费用最大流即可。(若答案小于2,则说明方案不存在)

而输出方案的话,则跑两次dfs即可。

方格取数问题

题意:

有一个 mn 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。

做法:

这是个经典的最小割套路题。国际象棋棋盘本身就是一个二分图,我们发现同色的方格无论怎么选都不会发生排斥。于是我们将黑白两种棋格分别置于左右两部,依据限制关系连边。然后建立超级源点与超级汇点,超级源点与左部图每个点连该点点权的边,超级汇点与右部图每个点连该点点权的边。求最小割即为最小舍弃的点权之和,用所有点权之和减去最小割即为答案。根据最大流-最小割定理,求最大流即可。

圆桌问题

题意:

有来自 m 个不同单位的代表参加一次国际会议。第 i 个单位派出了 r_i个代表。

会议的餐厅共有 n 张餐桌,第 ii 张餐桌可容纳 c_i 个代表就餐。

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

做法:

考虑将单位放在二分图的左部,餐桌放在二分图的右部。由于每个单位只能派出一个成员前往一个餐桌,故将所有单位与所有餐桌连流量限制为1的边。源点与单位连接限制为单位人数的边,餐桌与汇点连限制为餐桌人数的边,跑最大流即可。方案枚举中间的边即可。

骑士共存问题

题意:

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

做法:

和棋盘问题类似,但是此题加入了障碍,所以将源(汇)点与障碍点相连的边去掉即可,其余方法与棋盘取数问题同解。

网络流24题刷刷刷》有2条留言

留下回复