网络流24题刷刷刷

魔术球问题

题意：

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

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

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

做法

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

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

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

最长不下降子序列问题

题意：

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

1. 计算其最长不下降子序列的长度 s。
2. 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 s 的不下降子序列。
3. 如果允许在取出的序列中多次使用 x_1 和 x_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即可。

方格取数问题

题意：

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

做法：

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

圆桌问题

题意：

有来自 m 个不同单位的代表参加一次国际会议。第 i 个单位派出了 r_i个代表。
会议的餐厅共有 n 张餐桌，第 ii 张餐桌可容纳 c_i 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

做法：

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

骑士共存问题

题意：

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

做法：

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