Mato is No.1

网络流最让人不能忍受的不是模板，而是建模！尤其是某些题目里面需要搞一段很长的预处理才能开始写网络流……

最大闭合子图就是其中的一种。如果要求最大闭合子图的有向图里面有环就很囧了，因为在某些题目里（比如NOI2009的pvz），取点是有先后顺序的，因此环中的点一个也取不了（有的题则不是这样，子图里的点可以一次全部取来，这时对于环就有两种方案了：要么全取，要么一个不取，此时不用管环，直接进入网络流即可），不仅如此，根据闭合子图的定义，如果一个点i可以到达一个点j（注，是“可以到达”点j，也就是从i到j有路径），而点j属于某个环，那么点i也不能取，因此在预处理中需要把点i也删掉。以下将属于某个环中的点成为“环点”，将可以到达环点的点称为“环限制点”，这两种点在预处理中都要删除。

本沙茶以前用的一般方法是：先求图的传递闭包，找出所有的环点（能够到达自己的点），再从每个环点开始进行逆向遍历（将原图所有边反向，再遍历），找到所有的环限制点。该方法的时间复杂度高达O(N³)，且写起来也爆麻烦。

其实，真正用于去环的最佳方法是拓扑排序！！！

首先将原图的所有边反向，然后进行拓扑排序，所有遍历到的点是保留下来的点，而没有遍历到的点就是环点或环限制点，需要删除。
【证明：环点显然是不可能被遍历到的，而在反向后的新图中，对于一个环限制点j，必然存在一个环点i能够到达它，而i不能被遍历到，故j也不能被遍历到。除了这两种点外，其它的点的所有前趋必然也都不是环点或环限制点（否则这些点就成了环限制点），因此只要入度为0（不存在前趋）的点能够遍历到，这些点也能够遍历到，而入度为0的点显然能遍历到，故这些点也能被遍历到。证毕】
由于求反向图和拓扑排序都可以在O(M)时间内完成，整个去环过程的时间复杂度就是O(M)的。

下面附上NOI2009 pvz代码：（注意，本题的第9个点是一个超级大数据，最后建出来的网络的边数将会达到300000，故MAXM取150000，另外，本题必须使用Dinic，SAP会超）

【这次市选我挂得很惨……前3题全部爆0（骗分都米骗到）……就这种烂成绩还能进市队，可见合肥人之沙茶……】
最不该挂的是第一题。第一问就是个裸的最大闭合子图，关键就出在第二问上，要求最大闭合子图的最小容量。本沙茶后来才发现这竟然是PKU原题！（PKU2987），因为，最大流求出来的最大闭合子图一定是容量最小的！故第二问只要在求出最大流后来一次遍历，找到S可达的结点个数即可。

详细证明（转网上某神犇的）：
———————————————————————————————————————————————————最大权不可能是负数，当是0的情况，自然是一个点不选最优，下面探讨忽略0的情况。

         1：首先我假设有两个闭合子图都拥有相同的最大权，并且没有共同点，很容易证明不会出现这种情况，因为如果我们把两个闭合子图都选择上，那么最大权会变大。

         2：仍然假设有两个闭合子图都拥有相同的最大权，但是有共同点，即重叠的意思。根据闭合图的特点，这些共同点不是随意的，可以知道，只要有一个点相同，那么这个点的能到达的所有后续点都必定是共同点。所以会得出一个结论，两个闭合子图重叠，重叠的部分必然是1个或者多个不重叠闭合图。


    然后我们考虑不重叠的部分，这部分的点权和可以证明一定是非负。我们可以假设非重叠部分的点权和是负数，那么假如我们删掉这部分，只选取重叠部分（因为重叠部分肯定是闭合图），那么最大权也会变大，矛盾。所以非重叠部分点权和一定是非负数。
    下面继续探讨非重叠部分的性质。上面的证明已经得出他们的点权和一定是非负。下面先抛开点权和等于0的情况，先讨论正数的情况。
假设两个闭合子图的非重叠部分都是正数，那么把这两个部分加起来重新构成闭合图，最大权必然会变大，与假设的两个同为最大权的闭合图矛盾。固可以证明非重叠部分的点权和肯定是0。

    探讨到这部分，我们已经可以初步得出一个结论，就是一个最大权闭合子图的点数多少问题只能受到一些0权和子图（所有点权加起来等于0的子图）的干扰。

    重点来到这些0权和子图上。下面我们又来做一个假设，就是假设我们求出了一个最大权闭合子图，并且里面有包含到一些0权和子图。而我们这时候需要做的就是找到那些可以删去的0权和子图，当我们删去了所有的这些子图，那么点数就可以达到最小。

    关键来了。到底哪些0权和子图是可以删去的，哪些0权和子图是不可以删去的呢？

    根据闭合图的性质，我们要删除一个点，那么必须把所有能到达这个点的点删去。那么很清晰的看到要删除一个子图，必须保证在这个子图外没有任何一个点指向这个子图。也就是说这个子图是封闭的，只有出边，没有入边。



    最后一步，假如我们能证明在求解最大权闭合图的过程中保证不会选上这些0权和子图，那么这个证明就可以结束了。
通过最大流求解最大权闭合子图，我们把正点权和源点建边，边权为点权值，负点权和汇点建边，边权为点权绝对值。仔细分析求解最大流的过程，会发现一些东西。

    由于那些可选可不选的0权和子图是封闭的，没有入边的，那么在求解最大流的过程中，不可能有外部流补充，所以这些0权和子图的每个点与源或者汇的边都是满流的。





    最后求最大权闭合子图的点，方法是从源点开始通过非满流边搜索一个联通图，图内的点（除了源点）就是求出来的最大权闭合子图的点。而上面证明到0权和子图的点和源汇都是满流，并且没有入边，出边也没有流，那么肯定无法从源点搜索到。那么在求解的过程中这些0权和子图的点是肯定没有选上的。

   就此证毕。
   结论：通过最大流求解最大权闭合子图的问题，求出来的闭合子图点数也是最少的。

———————————————————————————————————————————————————
代码：

欧拉环：图中经过每条边一次且仅一次的环；
欧拉路径：图中经过每条边一次且仅一次的路径；
欧拉图：有至少一个欧拉环的图；
半欧拉图：没有欧拉环，但有至少一条欧拉路径的图。

【无向图】
一个无向图是欧拉图当且仅当该图是连通的（注意，不考虑图中度为0的点，因为它们的存在对于图中是否存在欧拉环、欧拉路径没有影响）且所有点的度数都是偶数；一个无向图是半欧拉图当且仅当该图是连通的且有且只有2个点的度数是奇数（此时这两个点只能作为欧拉路径的起点和终点）；

证明：因为任意一个点，欧拉环（或欧拉路径）从它这里进去多少次就要出来多少次，故(进去的次数+出来的次数)为偶数，又因为(进去的次数+出来的次数)=该点的度数（根据定义），所以该点的度数为偶数。

【有向图】
一个有向图是欧拉图当且仅当该图的基图（将所有有向边变为无向边后形成的无向图，这里同样不考虑度数为0的点）是连通的且所有点的入度等于出度；一个有向图是半欧拉图当且仅当该图的基图是连通的且有且只有一个点的入度比出度少1（作为欧拉路径的起点），有且只有一个点的入度比出度多1（作为终点），其余点的入度等于出度。

证明：与无向图证明类似，一个点进去多少次就要出来多少次。

【无向图、有向图中欧拉环的求法】
与二分图匹配算法类似，是一个深度优先遍历的过程，时间复杂度O(M)（因为一条边最多被访问一次）。核心代码（边是用边表存储的而不是邻接链表，因为无向图中需要对其逆向的边进行处理，在有向图中，可以用邻接链表存储边）：
要注意的是在res中写入是逆序的，所以初始的v应设成(边数-1)。
但是有一个问题是，这是递归实现的，当点数过多时有爆栈危险，所以最好使用非递归：
当原图是欧拉图时，一定可以求出欧拉回路。当原图是半欧拉图时，求欧拉路径，只要找到起点i和终点j，添加边<j, i>（或(j, i)），求欧拉环，再在求出的欧拉环中删除添加的新边即可。

不过最为BT的还不是这个，而是接下来的——
【混合图】
混合图（既有有向边又有无向边的图）中欧拉环、欧拉路径的判定需要借助网络流！

（1）欧拉环的判定：
一开始当然是判断原图的基图是否连通，若不连通则一定不存在欧拉环或欧拉路径（不考虑度数为0的点）。

其实，难点在于图中的无向边，需要对所有的无向边定向（指定一个方向，使之变为有向边），使整个图变成一个有向欧拉图（或有向半欧拉图）。若存在一个定向满足此条件，则原图是欧拉图（或半欧拉图）否则不是。关键就是如何定向？

首先给原图中的每条无向边随便指定一个方向（称为初始定向），将原图改为有向图G'，然后的任务就是改变G'中某些边的方向（当然是无向边转化来的，原混合图中的有向边不能动）使其满足每个点的入度等于出度。
设D[i]为G'中(点i的出度 - 点i的入度）。可以发现，在改变G'中边的方向的过程中，任何点的D值的奇偶性都不会发生改变（设将边<i, j>改为<j, i>，则i入度加1出度减1，j入度减1出度加1，两者之差加2或减2，奇偶性不变）！而最终要求的是每个点的入度等于出度，即每个点的D值都为0，是偶数，故可得：若初始定向得到的G'中任意一个点的D值是奇数，那么原图中一定不存在欧拉环！

若初始D值都是偶数，则将G'改装成网络：设立源点S和汇点T，对于每个D[i]>0的点i，连边<S, i>，容量为D[i]/2；对于每个D[j]<0的点j，连边<j, T>，容量为-D[j]/2；G'中的每条边在网络中仍保留，容量为1（表示该边最多只能被改变方向一次）。求这个网络的最大流，若S引出的所有边均满流，则原混合图是欧拉图，将网络中所有流量为1的中间边（就是不与S或T关联的边）在G'中改变方向，形成的新图G''一定是有向欧拉图；若S引出的边中有的没有满流，则原混合图不是欧拉图。

为什么能这样建图？
考虑网络中的一条增广路径S-->i-->...-->j-->T，将这条从i到j的路径在G'中全部反向，则：i的入度加1出度减1，j的入度减1出度加1，路径中其它点的入度出度均不变。而i是和S相连的，因此初始D[i]>0，即i的出度大于入度，故这样反向之后D[i]减少2；同理，j是和T相连的，这样反向之后D[j]增加2。因此，若最大流中边<S, i>满流（流量为初始D[i]/2），此时D[i]值就变成了0，也就是i的入度等于出度。因此只要使所有S引出的边全部满流，所有初始D值>0的点的D值将等于0，又因为将边变向后所有点的D值之和不变，所有初始D值小于0的点的D值也将等于0，而初始D值等于0的D点既不与S相连也不与T相连，所以它们是网络中的中间点，而中间点的流入量等于流出量，故它们的入度和出度一直不变，即D值一直为0。因此，整个图G'成为欧拉图。

（2）欧拉路径的判定：
首先可以想到的是枚举欧拉路径的起点i和终点j，然后在图中添加边<j, i>，再求图中是否有欧拉回路即可。但是，该算法的时间复杂度达到了O(M * 最大流的时间)，需要优化。
前面已经说过，在将边变向的过程中任何点的D值的奇偶性都不会改变，而一个有向图有欧拉路径的充要条件是基图连通且有且只有一个点的入度比出度少1（作为欧拉路径的起点），有且只有一个点的入度比出度多1（作为终点），其余点的入度等于出度。这就说明，先把图中的无向边随便定向，然后求每个点的D值，若有且只有两个点的初始D值为奇数，其余的点初始D值都为偶数，则有可能存在欧拉路径（否则不可能存在）。进一步，检查这两个初始D值为奇数的点，设为点i和点j，若有D[i]>0且D[j]<0，则i作起点j作终点（否则若D[i]与D[j]同号则不存在欧拉路径），连边<j, i>，求是否存在欧拉环即可（将求出的欧拉环中删去边<j, i>即可）。这样只需求一次最大流。

【典型例题】Sightseeing tour（PKU1637，ZJU1992）
本题就是求混合图的欧拉环问题，题目中已经说明图是连通的（Input的最后一句话），故不需判连通。
（本沙茶一开始把DFS中的l0 = aug中的"= aug"写漏了，TLE了N次）

在二分图最大匹配中，每个点（不管是X方点还是Y方点）最多只能和一条匹配边相关联，然而，我们经常遇到这种问题，即二分图匹配中一个点可以和多条匹配边相关联，但有上限，或者说，L_i表示点i最多可以和多少条匹配边相关联。

二分图多重匹配分为二分图多重最大匹配与二分图多重最优匹配两种，分别可以用最大流与最大费用最大流解决。

（1）二分图多重最大匹配：
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值的边，每个Y方点向T连一条容量为该Y方点L值的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），求该网络的最大流，就是该二分图多重最大匹配的值。

（2）二分图多重最优匹配：
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值、费用为0的边，每个Y方点向T连一条容量为该Y方点L值、费用为0的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），费用为该边的权值。求该网络的最大费用最大流，就是该二分图多重最优匹配的值。

例题：
【1】POJ1698 Alice's Chance
将电影作为X方点，每一天作为Y方点（最多50周，每周7天，所以共设350个Y方点），若第i个电影可以在第j天搞就连边(i, j)。每个X方点的L值为该电影总共要搞多少天，每个Y方点的L值为1（每天最多只能搞一个电影），然后求二分图多重最大匹配，若能使所有从源点连向X方点的边都满流，则输出Yes，否则输出No。
【2】POJ2112 Optimal Milking
先预处理求出每两个点（包括挤奶点和牛）间的最短距离，然后将所有挤奶点作为X方点（L值为该挤奶点最多可以容纳多少牛），所有牛作为Y方点（L值为1），X_i和Y_j间边的权值为这两个点之间的最短距离（若这两点间不存在路径则此处无边），然后问题就变成了求一个多重匹配，使得每个Y方点都有匹配点且匹配边中权值的最大值最小。
可以枚举最大边权值S，然后，原图中所有权值大于S的边都要删去。若此时图中存在符合要求的多重匹配，则S合法否则S不合法。由于S的合法性是单调的，所以可以二分枚举S。

今天终于搞懂了RMQ问题无比神犇的ST算法……

【离线RMQ问题】
题意：对于一个序列A[1..N]，共有M次提问，每次都是问A[l..r]（1<=l<=r<=N)中的最值，求出每次提问的答案。

（1）纯暴力枚举：O(NM)；
（2）树状数组：O(M(logN)^2)【见树状数组解决离线RMQ问题】
（3）ST算法：O(MlogN)……
ST算法是基于分块DP的。
设F[i][j]为A[i..(i+2^j-1)]（共2^j个元素）中的最值（前提是不能越界，即i+2^j-1 <= N），显然F可以通过DP的方式得到：
F[i][j] = min||max{F[i][j-1], F[i+2^(j-1)][j-1]}
边界：F[i][0]=A[i]。
DP求F的值的时间复杂度为O(NlogN)（一共只有NlogN个F值有意义）；

然后，对于求A[l..r]中的最值，只要将A[l..r]拆成若干连续的段，使得每段的长度都是2的整数次幂就行了，比如A[3..28]可以拆成A[3..18]、A[19..26]、A[27..28]三段，长度分别是16（2^4）、8（2^3）、2（2^1），所以min||max{A[3..28]} = min||max{F[3][4], F[19][3], F[27][1]}。
关键是怎么拆？方法：求出(r-l+1)（即A[l..r]的长度）的二进制形式，然后从高位到低位依次遍历，如果找到1位就加上目前的位对应的幂，如(28-3+1)=(11010)2，所以依次找到F[3][4]、F[3+2^4][3]、F[3+2^4+2^3][1]。注意此时需要预先设一个数组B，B[2^i]=i，以方便找到某个取出的幂对应的指数。
显然，最多只有logN段，所以一次提问的时间复杂度为O(logN)。

其实还有一种方法，就是先求出log(r-l+1)的值（下取整），设为x，然后F[l][x]和F[r-2^x+1][x]中的较大/较小值就是A[l..r]中的最值。这样，一次提问的时间复杂度就降到了O(1)。问题是，系统log函数灰常慢，也许算一次log函数值的时间已经超过了logN，这样显然得不偿失。所以仍然推荐上面的方法。

【核心代码（以求最小值为例，最大值类似）】
分段法：
求log值法：
求F数组值的预处理代码（注意，如果采用求log值的方法就不需要B数组了）：

【后经效率测试，发现当N=M=100000的随机数据中，两种方法都可以在0.4s以内得出正确结果，其中log值法比分段法略慢0.01s左右，相差不大，但考虑到“尽量少使用数学函数”的原则，仍推荐分段法】

依照CLJ神犇的指示，最近本沙茶决定开始被数据结构题虐……先找来了省内的一道题（就是这道囧）……

题目大意：求两个长度为5N的序列的最长公共子序列长度，在两个序列中，整数1~N分别都出现5次。1<=N<=20000。

【注：本沙茶一开始用线段树的，后来在看了CLJ神犇的标程（Orz！！）之后终于明白了树状数组解法囧……】

LCS问题的朴素时间复杂度为O(NM)。对于本题显然需要优化。
观察LCS的转移方程：
F[i][j] = F[i-1][j-1]+1（当A[i]==B[j]时）
F[i][j] = max{F[i-1][j], F[i][j-1]}（当A[i]!=B[j]时）

可以将F用滚动数组来表示，即设F'为上阶段的F（即F[i-1]），则本阶段的F（即F[i]）可以由F'求得：
F[j] = F'[j-1]+1（当A[i]==B[j]时）
F[j] = max{F'[j], F[j-1]}（当A[i]!=B[j]时）

进一步，这个F'其实都不用记录，只需在每一阶段更新一遍F即可：
F[j] = F[j-1]+1（当A[i]==B[j]时）
F[j] = max{F[j], F[j-1]}（当A[i]!=B[j]时）
不过需要逆序更新（保证F[j-1]是上一阶段的而不是本阶段的），这与01背包有点像。

由题意可以发现，A[i]==B[j]的出现次数极少，在每阶段中只会出现5次！我们可以预先求出这5个地方的值，然后对于其它的F[j]，其在本阶段的值其实就是它前面的最大值（max{F[1..j-1]}），又因为我们最后只需知道F[N']（N'=5N，即序列长度）即可，故可设计出以下算法：
一开始F[1..N]均为0，然后将以下内容执行N'次，第i次：
（1）求出B序列中与A[i]相等的5个元素的位置，设为S[1..5]；
（2）依次更新F[S[5..1]]，每个都更新为它前面的最大值加1（很容易知道为神马），其它的值暂时不管；

N'次执行完后，整个序列中的最大值就是F[N']的值。由于这个算法中出现的主要操作是改动一个指定位置元素的值和找一个前缀区间中的最大值，因此可以采用树状数组，时间复杂度O(NlogN）（线段树必TLE）。

【总结：在本题中使用了一种“推迟更新”的方法，即需要更新一个值时，先暂时不理它，等到需要引用到它的时候再更新。这种方法最常见的应用就是线段树的结点标记。不过要注意的是，如果该值的推迟更新会对它后面要更新的值带来问题（也就是，这些后更新的值需要引用该值的新值），就不能使用这种方法。在本题中，其它位置的值的改变只与这5个特殊的位置有关，与其它因素无关，故可以使用这种方法。】

树状数组与线段树不同，它只能直接支持前缀区间（[1..r]）或后缀区间（[l..N]）上的操作，而对于一般区间（[l..r]）上的操作则需要通过两步操作间接完成：先对[1..r]进行操作再对[1..l-1]进行反操作（如加c的反操作就是减c），对于加法操作这样可反的操作是可以，而对于求最值这样的不可反的操作（无法通过[1..r]的最值与[1..l-1]的最值得出[l..r]的最值），就没有办法了。其实，用树状数组是可以解决离线RMQ问题的，但时间复杂度不太理想（一次操作的理论时间复杂度达O((logN)^2)）。

方法是（这里C[i]表示i管辖的数组结点中的最值）：设r'为目前的右端点，一开始r'=r。每次找到r'管辖的数组结点中最左边的那个的下标（即r' - (r' & (-r')) + 1），设为x。若x>=l，则将C[r']与目前的最值比较、更新，再将r'设为(x-1)；若x<l，则调出A[r']的值与目前最值比较、更新，然后将r'减1。如此直至r'<l为止。

本算法编程复杂度极低，但由于时间效率较低，难以适应较大范围数据（N, M>100000基本上就TLE了）

树状数组在区间求和问题上有大用，其三种复杂度都比线段树要低很多……有关区间求和的问题主要有以下三个模型（以下设A[1..N]为一个长为N的序列，初始值为全0）：

（1）“改点求段”型，即对于序列A有以下操作：

【1】修改操作：将A[x]的值加上c；

【2】求和操作：求此时A[l..r]的和。

这是最容易的模型，不需要任何辅助数组。树状数组中从x开始不断减lowbit(x)（即x&(-x)）可以得到整个[1..x]的和，而从x开始不断加lowbit(x)则可以得到x的所有前趋。代码：

 

操作【1】：ADD(x, c);

操作【2】：SUM(r)-SUM(l-1)。

（2）“改段求点”型，即对于序列A有以下操作：

【1】修改操作：将A[l..r]之间的全部元素值加上c；

【2】求和操作：求此时A[x]的值。

这个模型中需要设置一个辅助数组B：B[i]表示A[1..i]到目前为止共被整体加了多少（或者可以说成，到目前为止的所有ADD(i, c)操作中c的总和）。

则可以发现，对于之前的所有ADD(x, c)操作，当且仅当x>=i时，该操作会对A[i]的值造成影响（将A[i]加上c），又由于初始A[i]=0，所以有A[i] = B[i..N]之和！而ADD(i, c)（将A[1..i]整体加上c），将B[i]加上c即可——只要对B数组进行操作就行了。

这样就把该模型转化成了“改点求段”型，只是有一点不同的是，SUM(x)不是求B[1..x]的和而是求B[x..N]的和，此时只需把ADD和SUM中的增减次序对调即可（模型1中是ADD加SUM减，这里是ADD减SUM加）。代码：

操作【1】：ADD(l-1, -c); ADD(r, c);

操作【2】：SUM(x)。

（3）“改段求段”型，即对于序列A有以下操作：

【1】修改操作：将A[l..r]之间的全部元素值加上c；

【2】求和操作：求此时A[l..r]的和。

这是最复杂的模型，需要两个辅助数组：B[i]表示A[1..i]到目前为止共被整体加了多少（和模型2中的一样），C[i]表示A[1..i]到目前为止共被整体加了多少的总和（或者说，C[i]=B[i]*i）。

对于ADD(x, c)，只要将B[x]加上c，同时C[x]加上c*x即可（根据C[x]和B[x]间的关系可得）；

而ADD(x, c)操作是这样影响A[1..i]的和的：若x<i，则会将A[1..i]的和加上x*c，否则（x>=i）会将A[1..i]的和加上i*c。也就是，A[1..i]之和 = B[i..N]之和 * i + C[1..i-1]之和。
这样对于B和C两个数组而言就变成了“改点求段”（不过B是求后缀和而C是求前缀和）。
另外，该模型中需要特别注意越界问题，即x=0时不能执行SUM_B操作和ADD_C操作！代码：


操作【1】：
ADD_B(r, c); ADD_C(r, c);
if (l > 1) {ADD_B(l - 1, -c); ADD_C(l - 1, -c);}

操作【2】：SUM(r) - SUM(l - 1)。

代码1：SAP单路增广（非递归）；

代码2：SAP多路增广（递归）；

代码3：Dinic单路增广（非递归）；

代码4：Dinic多路增广（递归）；

结果：

代码1：

代码2：

代码3：

 代码4：

结果：
SAP加了多路增广后，直接秒掉后2个点；
Dinic加了多路增广后效率差不多，还更低了一点……

（另外发现，SAP的多路增广不支持当前弧优化……这点和zkw费用流有点像囧……不过效率影响不大……）

总算找到一个相对安静的地方了……好高欣啊……

希望在这里，本沙茶不要再听到太多害人的Orz声（当然，只是别Orz我，神犇们本来就是给人Orz的囧）……

现在没神马动力……来这里……就有动力了囧……