最大流的一个基本算法就是Ford-Fulkerson，基本的思路是：每次寻找一条增广路，记下增广路上最小的可改进量，并改进这条增广路，如此循环直到不存在增广路。

可以发现，Ford-Fulkerson有点浪费时间，SAP应用标号思想进行优化。另外对于单流增广，它必须找到一条完整的增广路之后再进行增广，如果存在一条岔路，那么它必须分作好几次才能做完。因此多流增广就有了：对于一个节点，在其可增广范围内对其相邻节点递归增广。

网络流的题目在构图的时候有个小技巧，原先需要使用剩余网络，必须有两张图存储。而实际应用中，只要每一条有向边都有一条跟它对应的反向边，且这两条边的流量值和等于容量限制即可。这样只要在一张图中存储即可，省去不少麻烦。自然，改进这条路的时候，将一条边上的流量+Delta，另一条边-Delta。

关于Ford-Fulkerson和SAP的基本思想可以参考附件的两个课件。下面贴出来几题最大流的题目，详细的Ford-Fulkerson和SAP实现见程序，可以参考注释。

[PKU1273]Drainage Ditches

赤裸裸的网络流，下面的程序是Ford-Fulkerson算法。

Read on →

赤裸裸的单调队列。分别用一个单调递减和一个单调递增的队列来维护最大值和最小值，当队头元素的位置与i的差超过k那就丢弃头。每一次插入i时都要维护单调性，之后输入队列的头元素。

下面的程序用了STL的双端队列deque，和写数组没什么差别，略去了头尾指针而已。其实STL有优先队列，只不过应用在这题上面还得写个类才能保证头指针的移动，过于麻烦，还不如自己实现单调队列。 Read on →

这题朴素的方法很简单，根据题目要求每一次把答案加上min{abs(a[i]-a[j]) (jRead on →

线段树（Segment Tree）是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b]。因此线段树是满二叉树，最后的子节点数目为N，即整个线段区间的长度 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。——维基百科

其实按照我的理解，线段树不是二叉搜索树，也不是完全二叉树，只不过是按照完全二叉树存储而已，而且这样存储空间复杂度(4N)。 上星期在练线段树（五个晚上+1整天才做了6题T_T），下面就把这6题的解题报告贴出来。

1. PKU3264

这题作为线段树入门题目再合适不过了，这题就是求区间最小/最大值之差，用RMQ比方说ST算法也可以过，不过貌似线段树更快点。此题不涉及修改，练习从数组构建线段树和线段树的查询。 Read on →

一个月封闭连同2天的比赛就这么过去了。

封闭

这次封闭感觉很奇怪，因为玩的时间很长，做正事的时间倒是少了很多。到了去福州的前一天，按理说应该认真复习总结的，但是却很奇葩的整个机房异常欢乐。我是觉得准备有点不足啊，4个星期，只是把NOIP历届试题做完了，草草的把动规2做了一半，最后连大表的题目都没做完。各种专题都没练过，模拟基本都挂……不过习惯各种挂，倒是可以使人淡定。最后是很心虚地上了考场，很淡定的做题。

集训的时候我把机械键盘带来学校了（现在不打算带回家了），由于打字的时候按一个键会响两次，碰巧我打输入输出文件的时候又比较快，所以开始时众人抱怨道：压力很大！不过后来大家就习惯了……每日的CS十分欢乐（不会Dota，但是估计Dota党也很欢乐）…… Read on →

高精重要性没的说，最近爱上了用操作符重载来写高精，干脆把高精都整理出来一个程序里面。下面这个程序包括了：

1. 字符串转高精数组
2. 高精+高精
3. 高精+低精
4. 高精-高精（答案必须为非负数）
5. 高精*高精
6. 高精*低精
7. 高精div低精
8. 高精数之间的<=、>=、<、>、=判断
9. 高精数的输出
10. 以上全都是压4位
11. 一个小小的demo

可以发现操作符重载之后运算符的优先级和结合性不变。 参数表中的const很重要，否则复制数组会浪费很多时间。另外能压四位的高精不得不注意一下字符串读入，有时候长度是超过255的，注意改成ansistring。 程序如下： Read on →

题目的意思就是给定一张有根图，根据所给规则计算费用之和。这题有点像bzoj1131，但更简单，因为不用换根。

我们可以假定以1为根，计算出以i为根节点的子树的节点数son[i]。统计时对于边(u,v)，假设u为以1为根的树中v的父亲（反过来也一样），那么费用就要加上son[v]+(n-son[v])。 Read on →

这题就相当于：求把n块给定的木板合并成一个大木板所需的最少花费。

因为n<=20000，nlogn的算法可以轻松过。维护一个堆来保存每块木板的长度。每次从堆中取出前两个，将这两个合并，再放入堆中。如此反复，直至堆中只有一个元素。

其实这题就是NOIP的合并果子……只要把数据范围改下，直接交上去都能AC…… Read on →

从上往下掉落，这就意味着如果对于管子ia[i]，那么a[j]应该被修正为a[i]（大了也没用）。这样一来，读入的管子将变成一个上大下小的漏斗。将a[i]依次压入栈中，对于扔下的盘子，不断处栈直至找到一个能够容纳这个盘子的管子。 Read on →

方法一：st算法。复杂度O(nlogn)，如果题目给的是10s可以轻松过，5s就难了。

方法二：赤裸裸的单调队列。

维护两个单调队列，一个Qmax单调递减，一个Qmin单调递增。对于这两个队列，如果队列的头的位置与i的距离大于i-m+1，那么丢弃头。每个a[i]进来，维护两个队列的性质，进队。如果Qmax的头的值-Qmin的头的值<阈值，输出。 Read on →