最近一直很忙,为了节省时间,从今以后的题解会 一个专题 写一篇。

刷了一些题后,有了以下总结：

模型要点:

1.构造流量平衡,在满足流量平衡的情况下,找到要让什么最大。

2.一般用于判断性问题,即所有从源点流出的边满流(或者所有流入汇点的边满流).所以往往和二分答案结合起来使用。

3.如果答案假设为i+1的时候的图仅仅比假设答案为i的时候的图多了一些点或者边,那么可以在假设答案为i的图 跑过最大流后,加上相应的点和边,继续跑最大流.这样顺序枚举答案,避免了每次重新做最大流和重新构图，许多时候效率比二分答案高。

相关题目:

1.飞行员配对方案 (网络流24题)：

 二分图匹配的模型.

2.最小路径覆盖（网络流24题）：

由于是DAG,可以发现选取路径数等于顶点数减去选取的边数。每个点只能在一条路径上,因此除了起点和终点,每个点的入度出度都为1. 因此转化为二分图,把每个点i拆成2个点<s_i,t_i>(分别表示点i的入度和出度),对于每条边<i,j>，连边<t_i,s_j>(让i出度和j入度+1). 然后连<S,t_i> <s_i,T>,每个点的入度出度都只能用一次,那不就是二分图匹配的模型了？ 如果要输出方案,找到所有si没有匹配的点(即没有入度)当做起点,沿着匹配边dfs寻找就可以了.

3.魔术球(网络流24题)：

题目大意：有n根柱子，在这n根柱子中依次放入编号为1，2，3，……的球，每次只能在某根柱子的最上面放球，在同一根柱子中，任何2个相邻球的编号之和为完全平方数。求在n根柱子上最多能放多少个球。

注意题目中是依次放,所以编号小的只能放在编号大的下面。所以对于球i,找到所有满足(i+j)是完全平方数且j>i的球j,连一条边<i,j>. 然后二分答案，做最小路径覆盖与n比较。 这样做的前提是按编号从小到大放球,可见题中"依次"的重要性。

4.最长递增子序列（网络流24题）

题目描述：

 给定正整数序列x₁, x₂, ..., x_n。
（1）计算其最长递增（非降，允许有相等元素）子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。

这题当时没想出来,构图挺巧妙的.

第一问:dp就不多说了,F[i]表示以i结尾的LIS。

第二问:利用第一问dp的数组。 对于任意i<j，只有当 A[i]<A[j] 且 F[i]+1==F[j]的时候才连边<i,j>。由于每个点只能用一次,所以拆成两个点,增加点流量限制为1.

第三问:只要去掉第二问中 点1和点N的流量限制就可以了。

5.星际转移问题（网络流24题）

题目大意：

有N个人在地球(源点S)，要用公交飞船送到（汇点T），然后告诉你每个飞船的周期和路线,求最少要多少天完成目标。

这题让我第一次接触了分层图的思想。如果不拆点,那么没法表示边,因为根据周期边是会"跑"的。根据lrj《训练指南》上的做法,假设答案是k天，那么把一个点拆成k+1个点,即表示第i天这个点的状态。 那么就可能根据公交飞船的周期和路线来连边.比如有一个飞船,第3天在i点，第4天在j点,那么连边<i₃,j₄>.做最大流判断是否能达成目标就可以了。 至于k,二分或者枚举都可以,但是枚举应该会快一些。 

最大流 总结&&做题记录