flow 24 problems

搭配飞行员

题目描述

正副驾驶员必须搭配飞行，问如何搭配使得出航的飞机最多。

解题思路

对可以相互配合的正驾驶员和副驾驶员建边，跑最大流即可。

太空飞行计划

题目描述

每个实验都要使用一定的仪器，不同实验可以共享仪器。实验有经费，仪器有价格，选择实验使得收益最大。

解题思路

这是一个trick，即求解最大权闭合子图的答案。答案应该是选择的实验减去选择的仪器所得到的贡献。也就是所有实验的答案减去不选择的实验与选择的仪器的答案和。

我们考虑最小割。超级源点到实验连边，权值为实验的费用；实验到仪器连边，权值正无穷；仪器到超级汇点连边，权值为仪器的费用。那么我们的割边就是所需要的答案。

最后，我们考虑最小割的意义。与S在同一个集合中的点代表选择的点，与T在同一个集合中的点代表不选择的点。因此可以直接输出净收益最大的实验计划。

最小路径覆盖

题目描述

设是的一个简单路(顶点不相交)的集合。如果中的每个顶点恰好在的一条路上，则称是的一个路径覆盖。中路径可以从的任何一个顶点开始，长度也是任意的，可以为。求最小路径覆盖。

解题思路

我们考虑一条路径的特点，即每个点都只能有最多一条入边和一条出边。我们可以将答案初始化为所有节点都是孤立路径，每次连一条边就是做一次路径合并。

具体操作时，将每个点拆成两个点，分别表示入边节点和出边节点。每一次加入一条边，意味着两条路径被合并。因此只需要跑最大流即可。其中满流的边就是被选中的边。

如果是可相交的最大流，可以先用Floyd算法求闭包，对于可达的所有节点均连边，再跑最大流。

魔术球

题目描述

根柱子，按照顺序依次放球，要求每次只能在某根柱子的最上面放球，同一根柱子中相邻的两个球的编号和为完全平方数，计算根柱子上最多能放多少球。

解题思路

我们将问题转化为给定个球，问最少需要多少个柱子。

这样将问题转化为最小路径覆盖问题。

复杂度在于枚举球的个数。我们可以很显然的考虑二分来解决这个问题。

但是本题存在一种更优雅的解法。我们考虑动态向图中加点。加点后相当于在残量网络上继续跑网络流。这样就避免了重复计算。

注意，在残量网络中跑得的结果需要与之前的结果相加，作为判断的标准。

圆桌聚餐

题目描述

每个单位的代表数目和餐桌可容纳的代表数各异，将同一个单位的代表安排在不同的桌子，求解一种方案。

解题思路

每个单位向每张桌子连边，容量为1。源点向每个单位连边，容量为代表数目。每张桌子向汇点连边，容量为可容纳的代表数目。跑最大流即可。方案为容量为0的边的集合。

最长递增子序列

题目描述

给定子序列，求最长非严格递增子序列的长度；求最多能取出多少个最长的子序列（不可重复使用点）；求在第一个和最后一个数能重复使用的情况下，最多能取出多少个最长的子序列。

解题思路

最长非严格递增子序列直接dp即可。

取子序列的过程我们将可以转移的点之间连边，然后从的点流入流量，的点流出流量。最后的总流量就是答案。但是我们必须保证一个点只能被选择一次，因此我们将一个点拆成两个点，边长度为1，这样就能限制从该点流出的流量，保证只有一条路径能从该点通过。

对于下一问，无疑是将和两个点取消如上限制，同时扩大流入和流出的管道的容量，在残量网络上跑即可。

试题库

题目描述

给定每个试题属于的类别，每个类别选出一定数量的试题，不能重复，要求给出选择的方案。

解题思路

从源点到每个试题连边，容量为1。每个试题向对应的类别连边，容量为1。每个类别向汇点连边，容量为所需要选择的试题数。跑最大流，如果最大流等于所需要选择的试题数之和，那么答案存在。方案就是类别向题目连接的反向边中流量为1的边。

方格取数

题目描述

在一个的方格中填有若干数，从方格中取数，任意两个数所在方格没有公共边，且取出的数的总和最大，求最大的和。

解题思路

首先可以发现，对于任意的有公共边的格子，它们将属于两个不同的集合。我们将任意格子与它有公共边的格子连边，可以得到一个二分图。

我们知道，所需要的答案就是总的答案和减去不选择的格子的答案。我们要让后者最小，考虑最小割。

二分图内的边容量赋为正无穷。从源点到二分图一侧连边，容量为对应值的权值。二分图另一侧节点向汇点连边，容量同样为权值。考虑割边的含义。对于与源点相连的一侧，割边表明不选择该节点。对于与汇点相连的一侧，表明我们选择了与之相连的二分图节点之一，该节点不能选择，会在答案中被剪去。