玄学算法/精彩DS总结 Tascho/Memairos

这里的内容都是一些我高一学过的算法。 果然高一学过的科技只有到高二才能明白那是在干什么。 ## $1.Link-Cut\ Tree(including\ Splay)$ **$Attention:FlashHu$博客中的$LCT$图片仅为示意图，不保证正确性。** $LCT$是一种奇妙的数据结构。尽管其理论复杂度是$O(m\log n)$，但其优秀的常数使得其可以媲美$O(m\log^2 n)$甚至$O(m\log^3 n)$。 本质上，$LCT$是一种轻重链剖分，使用$Splay$森林来对它的所有重链进行维护。每一棵$Splay$会维护一个以深度为下标递增的链（将其缩成一棵二叉排序树的形式），$splay$的目的是为了保证其相关操作的复杂度~~，所以你或许可以用一些其他的数据结构比如$fhq\ treap$之类的来维护这些东西~~。 $LCT$有一些优美的性质： 每个点只会被包含在一棵$Splay$中； 每棵$Splay$的父亲是**这棵$Splay$中序遍历**最靠前的点在原树上的父亲，在一开始是原树上链顶的父亲； 对于任意一个被$splay$到根的点来说，它的左儿子比它深度小，右儿子比它深度大。 ### $Construction:$ ### $rotate$ $Splay$是依靠旋转来维持平衡的。 旋转主要涉及$x,y=fa[x],z=fa[y],side=(son[y][1]==x)$。 如果$y$非根，那么$son[z][son[z][1]==y]=x$。 无论$z$有没有，$fa[x]=z$。 然后$y$的儿子$son[y][side]=x$的反儿子$son[x][side\wedge1],son[x][side\wedge 1]=y,fa[y]=x$。 最后$pushup(y),pushup(x)$，因为$y$是$x$儿子。 ### $splay$ 先来讲讲它的基石操作$splay$。 与$Splay$的$splay$不同，$LCT$的$Splay$一定会把它旋转到当前$Splay$的根。 需要注意$Splay$前是要$pushdown$翻转标记的，不然会错误$splay$。 ### $isroot$ 如果这个点是根，那么它父亲的左儿子和右儿子都不会是它。 直接判一下就可以了。 ### $access$ 最核心的操作。 这个操作的意义是，从这个点向上拉一条重链，满足**这条链的两个端点分别为根节点和当前节点。**也就是说，这个点下面的重链要断掉。 具体来说，我们每次暴跳父亲，让父亲$splay$到根，然后每次直接把父亲的右儿子设为它，因为原来的右儿子显然深度不会小于它，所以直接把那条重链断掉。注意一开始把右儿子设为0，而且信息要$pushup$。 ### $makeroot$ 换根操作，顾名思义就是把根换上去。 首先我们$access$一下，然后$splay$它到根的位置。 根据$access$的定义，显然我们可以发现这个点就是深度最深的点，也就是没有右儿子。 那么我们直接把整棵$splay$翻过去就可以了。这样这个点就是深度最小的。 但是我们注意到如果直接翻复杂度或许是$O(mn)$的，那么我们需要给它打一个标记。 **需要注意跟线段树一样，打标记的那个时候要修改一下当前的状态。** ### $findroot$ 这个东西是用来找到在整个原树中的根。 首先我们$access$，然后$splay$，那么此时的$x$就是顶端，只要一直往左儿子走就能找到深度最小的，也就是根节点。 **注意边走一定要边$pushdown$**。如果题目只有合并没有分离，可以考虑用并查集维护。 ### $link$ 首先要判新加的边是否合法。 先$makeroot(x)$，如果$findroot(y)==x$显然是不合法的，否则让$fa[x]=y$。 为什么这样是正确的呢？因为此时$x$已经是中序遍历最靠前的点了，那么直接这样连轻边是没问题的。 **$link$后不能$pushup(y)!$尽管看似$pushup(y)$是无意义的行为，但其会导致错误。原因不明。** ### $cut$ 首先要判要删的边是否合法。 如果合法，那么$makeroot(x),access(y),splay(y)$，$x$一定是$y$的左儿子。 然后以下三种情况都是不合法的： $1.findroot(y)!=x$； $2.fa[x]!=y$； $3.son[x][1]$有值。 注意$cut$之后要$pushup$。 ### $split$ 主要作用是拉出一条原树上的链中的信息。 $makeroot(x),access(y),splay(y)$即可。此时$y$上的信息就是整条链的信息。 ### $pushup,pushdown$ $pushup$的主要作用是将链上信息上传。 $pushdown$的主要作用是执行翻转标记，同时将链修改信息下传。 ### $Application:$ ### $chain$ 链信息是$LCT$最基本的操作。直接$pushup$（如果信息可加）。 ### $EBCC$ 此处$EBCC$指的是边双。 维护$EBCC$的方法比较简单：每新加一条边，首先判一下两点是否在一个连通块里，如果不是就直接连，否则如果两点不在一个边双里就把两点链上的所有点全部缩在一个点上，注意最后还要把这个点的儿子清掉保证复杂度。 ### $MST$ 维护最小生成树是基于贪心的思想。 直接一条一条加，维护一个链上边权最大值。 如果两个点在一个连通块里了就比较一下链上最大值是否大于这条边，如果是就直接替换。 如果有删边的$MST$怎么办？有一种非常暴力的方法就是套上线段树分治，遍历当前区间的时候，每次如果要换边我们就把换边记下来，出去之后再还原。虽然是$O(m\log^2 n)$，但常数大概十分巨大。存在区间可以用哈希表之类的记一下。 ### $connection$ 维护连通性也是基于贪心的思想。 实际上维护带删边的连通块我们最重要的问题就是删除一条边之后怎么维护原来环的连通性如何。 那么我们可以维护以删除时间为权值的最大生成树~~MST~~，那么每次成环就直接把最小边删掉，这样遇到删边的话，如果已经被删过就不用管，否则就可以直接删边而不用担心环的问题了，因为你之前的环边都已经被删掉了。 ### $subtree$ 维护子树信息实际上就是在维护虚子树信息，因为实子树的你已经维护好了。 为了方便地维护子树信息，影响子树信息的操作要注意一下： ### $subtree-access$ $access$会直接改变虚实儿子的关系，所以维护信息的时候要改一下。 譬如维护$siz$，用$vsiz$表示虚子树$siz$，那么$access$的时候，$vsiz[x]+=siz[son[x][1]]-siz[y],son[x][1]=y$；$pushup$就可以直接$siz[x]=siz[son[x][0]]+siz[son[x][1]]+vsiz[x]+1$。 ### $subtree-link$ 如果$link$像原来那样，直接$fa[x]=y$的话，那么$link$会影响$y$的所有父亲。 那么我们$makeroot(y)$，就只会影响$y$了。 注意搞完之后要$pushup(y)$。 ### $nonmakeroot-link$ ## $2.Suffix\ Automaton$ 后缀自动机是一种有限状态自动机，其能够接受给定字符串的所有**子串**。之所以不是“后缀”，是因为其对每个字符的所有后缀都可以接受，那就是子串了。 后缀自动机的时间、空间复杂度均为$O(n)$，状态/结点数不超过$2n-1$，转移数（包括后缀链接）不超过$3n-4$。 ### $Properties:$ 后缀自动机分为两部分——$DAWG(Directly\ Acyclic\ Word\ Graph)$和$Parent\ Tree/Suffix\ Links$。$parent$树的性质十分优秀。 ### $node$ ~~湖南蚊子Rank1：你最好把每个结点当成一个单词~~ 后缀自动机的结点可能代表多个~~单词~~字符串，这些字符串的长度一定会为公差为1的等差数列，且满足长度小的是长度大的后缀。它们的$right$集合相同。 ### $transfer\ edge$ 转移边构成了$DAWG$。一条转移边对应一个字符，一条转移边$c$一定是某个字符串$w$所在的节向$w+c$连接的。**但同时要注意的是，转移边连接的两个结点可以代表多个字符串，某些字符串之间并不具有包含关系。** ### $right/end-pos\ set$ $endpos/right$集合的包含关系实际上形成了$parent$树。 某个子串$S$的在原串上的出现位置（指的是子串末尾所在的位置）集合就是$right(S)$。很显然，会有许多字符串拥有相同的$right$集合。拥有相同$right$集合的子串会被归到一个节点。 ### $suffix\ link$ 后缀链接构成了$parent$树。若定义$len(x)$为结点$x$所代表的最长字符串，$minlen(x)$为最短字符串，则$len(link(x))+1=minlen(x)$，且$right(x)\subseteq right(link(x))$。利用这个性质，我们能很方便地识别子串。 显然这个点表示的字符串个数就是$len(x)-len(link(x))$。 ### $Construction:$ 后缀自动机的主流构造算法是一个在线的增量算法。但不要认为这个算法能在线维护$right$，因为$parent$树的结构会发生改变。在线维护$\vert right\vert$需要$LCT$，维护$right$则需要可持久化线段树套$LCT$。 **下面介绍算法的主要流程**： 首先我们设已经建好了串$S$的$SAM$，此时最后一个状态为$las$，当前加入一个字符$x$，状态为$cur$。那么根据$SAM$的定义，此时我们已经增加了$\vert S\vert+1$个后缀。 我们沿$link$往上跳，如果跳到的结点没有$x$的转移，就直接给它加上这么一个转移。 如果在一路上都没有出现$x$的转移，那么$link(cur)=0$。显然不会出现一个状态$c$满足$right(x)\subseteq right(c)$。 如果出现，那么意味着当前增加的某个后缀已经在$S$中出现过了。 我们假设这个**从下往上第一个**出现了$x$的转移的状态为$p$，它转移之后的状态为$q$。此时我们需要分类讨论。 如果$len(q)=len(p)+1$，那么意味着$q$表示的最长字符串也就是$p$表示的最长字符串后面加一个字符$x$。显然，因为$p$表示的所有字符串都是$las$的后缀，那么$q$表示的所有字符串肯定也是$cur$的后缀，加上又是第一个出现的，那么显然可以让$link(cur)=q$。 但还有另一种情况，也就是说$len(q)>len(p)+1$。此时意味着$q$表示的最长字符串并不是$p$表示的最长字符串加一个字符$x$。也就是说，**这个结点代表的某些字符串可能并非$cur$的后缀。**为了规避这种情况，我们需要对$link$进行一点修改。 首先我们蒯一个结点$clone$，这个结点与$q$的所有信息都一样，除了$len(clone)=len(p)+1$。**在实际意义上，这么做是为了使一定是$cur$后缀（也就是第一种情况）和不一定是$cur$后缀的那些字符串分离开来。** 分离之后，我们就把$link(cur)=clone$，正确性同第一种情况。然后，**此时的$clone$包含的所有字符串显然都是$q$的后缀**，所以我们继续跳$p$的$link$，把所有转移到$q$这个状态的结点都转移向$clone$，并且$link(q)=clone$。 最后，将$las=cur$，$S+x$的$SAM$便构造完成了。 ### $Application:$ ### $SA\ Construction$ 这是一种$O(n)$构建$SA$的方法。常数未与$DC3$对比，但代码难度小于倍增和$DC3$。 首先我们可以发现，反串的$parent$树就是原串的后缀树。 那么有了后缀树，我们怎么求后缀数组呢？ 我们直接按字典序$dfs$后缀树，如果遇到了一个合法后缀$x$，那么结点$x$的$sa(x)$就是它的$dfn$。 至于怎么按字典序有一点细节~~，之后我写了再说吧~~。 实际上，你需要注意后缀树与反串$parent$树虽然形态一模一样，但是你后缀树的一条转移边上的串其实是反串$parent$**树上每个节点代表的串的一部分，而且串的形态是正串的形态而不是反串。因此你不能直接在构造**$SAM$**时求出一个节点的字典，而是需要一些操作。** 具体来说，我们在构建反串$SAM$时记录一下$cur$的$right$**在原串中的位置**，然后我们考虑$link(u)\to u$这条边表示的串实际上是**这个结点表示的最长串的反串去掉**$link(u)$**中已有的部分。** 那我们把上面的位置求出来，每次建后缀树边的时候就可以算出这条边的字典了。 ### $Generalized\ SAM$ 广义后缀自动机用于模式串可能有多个，或者干脆就是一棵$Trie$的时候。 每建完一个串直接把$las$指向$0$即可；如果是$Trie$，从每个叶子结点作为根，将这棵树建到$SAM$里，每次$extend$返回当前的结点位置会更加方便。 **注意建广义$SAM$的时候要判当前转移的这个结点是否已经存在。如果不判，会建一个新的点，并且$link$到那个存在的结点上去（可以模拟一下过程）。在$[ZJOI2015]$诸神眷顾的幻想乡，以及$[bzoj3277]$串中，由于其统计的信息是$len(x)-len(link(x))$，又因为新建结点的$len(x)=len(link(x))$，所以它对答案不会有贡献，因此乍一看是没有问题的。** ### $Maintain\ \vert right\vert$ 首先有一个结论是$\vert right(x)\vert=\sum\vert right(son[x])\vert+\vert oriright(x)\vert$，这个结论可以看看下面从https://www.cnblogs.com/Robert-Yuan/p/5591627.html 蒯过来的图。 **注意每个构造$SAM$时新建的结点$cur$都会对其和其祖先上的$\vert right\vert$造成$1$的贡献，所以就不止是叶子个数和了。这个可以举例$abcabc$，一条链上也多了一个$\vert right\vert$。**  静态维护$\vert right\vert$只需要$dfs\ parent$树就可以了。当然我们有更方便的方法，直接按$len$排序然后倒着循环直接添加到它的父亲。 动态维护$\vert right\vert$的话，由于$parent$树结构会随时变动，不能在线更新答案。 但我们可以考虑新建的那个结点会对$parent$树上的祖先全部$+1$（这样不用维护子树和~~单点修改子树查询转化为链修改单点查询的老套路~~），于是我们可以在将后缀链接的改变转化为$link,cut$，在这个过程中可以直接进行链修改，给对应点打标记就可以了。 ### $Maintain\ right$ 静态维护$right$很简单，直接上线段树合并维护即可。 动态维护$right\cdots\cdots$应该是差不多的链加思路，用$LCT$套个可持久化线段树修改就可以了。链加标记是打在线段树外面的。 ## $3.Network\ Flow$ 网络流的内容十分繁杂，先从定义讲起吧。 ### $Definition:$ ### 网络 网络是一个有向图，其中有一个源点$S$，汇点$T$。源点与汇点不需要遵守流量守恒。**在实际建模中$S$不一定没有入边，$T$不一定没有出边。** 网络上的每条边称为弧，每条弧上都有一个容量。 ### 流（下文中流量为$F(low)$，容量为$C(apacity)$） 网络流指的是所有弧上流量的集合。它有三个基本的性质： **流量限制：**$F_i\le C_i$，显然。 **流量守恒：**$\sum_{x,x\to u}F_{x\to u}=\sum_{v,u\to v}F_{u\to v}$。 **反对称性：**$F_{u\to v}=-F_{v\to u}$。 最大流指的是最大的网络流。 ### 割 割指的是一些边的集合$C$，满足这个图去掉割上的边之后会被分成两个点集。 网络流上的割指的是将$S,T$划分成两个点集的割。其中简单割指的是割边各自都与$S/T$相连的割。 带权图上的割的权值就是集合内边权和。**割的权值往往也简称为割。在网络上，割的权值是容量。** 最小割指的是权值最小的割。 ### 残量网络 残量网络=容量网络-流量网络。其是网络流问题中最为中最为常用的网络。 ### 增广路$/Augmenting\ Path$ 增广路指的是一条$S\to T$的路径，且满足这条路径上的残量始终为**正 $(>0)$**。 如果将残量为正的边设为可行边，那么直接$BFS/DFS$就能够得到一条增广路。 可以证明，最多$O(nm)$次增广就可以得到最大流。 相关证明（感性）可以看https://www.cnblogs.com/zwfymqz/p/8277487.html ### 增广路定理$/Augmenting\ Path\ Theorem$ 网络流达到最大流当且仅当当前图内已没有增广路。 不会证明。 ### 最大流最小割定理 首先我们需要阐述为什么流与割之间是有关系的。 很显然，任意一个流$\le$任意一个割。然后，我们可以构造出最大流对应的割。（其实对于任意一个流我们都能构造出对应的割，因为割的净流等于网络的流量。证明也很简单，首先网络流的大小显然等于$S$出来的流的大小，然后这个流肯定要经过割上的边才能流向另一边，因此割的净流等于网络的流量。） 假定我们求出了最大流。那么根据增广路定理，此时残量网络上应该已经没有任意一条$S\to T$路径满足路径上的每条边都有残量。否则我们可以继续增广，使流量变大。也就是说，此时$S,T$已经不再连通。 因此，我们将$S$能够到达的点集设为$A$，$T$能到达的点集设为$B$（显然$A\cap B=\varnothing$），那么$A\to B$的边都必须满流。 可以看出，$A\to B$的所有满流边流量之和就是该网络的最大流，将这些边的集合作为一个割，我们就可以得到最大流对应的割。下面证明这个割就是最小割。下文中，用$C_{S,T},F_{S,T}$分别表示割的容量和净流。 首先我们可以推出任意一个割$\ge$任意一个流：$C_{S,T}\ge F_{S,T}=f_{S,T}$。因为割的净流$\le$割的容量，所以这个是正确的。 那么流的上界就是最小割，而因为我们在最大流时取到了一个割，这个割又满足$F=C$，那么这个割肯定就是最小割。 **注意，并不是所有的满流边都在割上，有些点是既不在$A$里又不在$B$里的，这些点对应的满流边是没有必要取的。当然最小割上的边都是满流边。** ### $Construction:$ ~~当然不是网络流建模的总结，而是有关网络流求解算法的内容。~~ 最大流算法有两种思想：第一种是增广路思想，也就是$Ford-Fulkerson$方法；第二种是预流推进思想，譬如著名~~（？）~~的$HLPP$（高标预流推进）算法就是这个思想。 下面主要讲述$Dinic$算法的求解最大流过程。因为$Dinic$能在残量网络上继续增广，所以比$ISAP$适用性更强。 ### $Edmonds-Karp$ $\cdots\cdots$当然，在这之前，还是要讲一下朴素的最大流算法。 首先找到一条增广路，之后找到这条路上的最小残量$mincap$。 然后我们开始增广，对增广路上的每条路径的残量减去$mincap$，同时加到最大流$flow$上；**然后让反向弧的残量加上$mincap$。** 为什么要让反向弧加上$mincap$呢？因为我们某次的增广后结果**可能并没有出现在最大流里**，因此我们需要**撤销**某次增广给某些弧带来的**某些**影响（并不一定是全部的影响）。 举个栗子，   （图片出自https://www.cnblogs.com/ZJUT-jiangnan/p/3632525.html） 可以看到，第一幅图是我们可能选取的一种增广路，然而它增广之后就没有可增广的路了，但它显然不是最大流。在这种情况下，我们需要撤销$2\to 3$这条弧的流量，于是在之前我们给它的反向弧$+1$，那么此时就出现了一条$1\to 3\to 2\to 4$的新增广路，此时达到了最大流。 在实际上，$2-3$这条边其实最后是没有流量的，因为反向弧给它抵消了。当然在实际情况中我们并不一定需要完全抵消那条弧的流量，可能只是撤回了一部分可以理解成让这部分撤回的流量走另一条边，让这条边的残量再空出来点方便接下来的增广。脑补一下就可以发现这样~~大概~~一定是能找到最优解的。 根据上文我们提到的性质，它的最劣复杂度$O(nm^2)$。 ### $Dinic$ 显然上面的复杂度非常劣。我们需要更优秀的做法来解决最大流问题，于是就有了$Dinic$算法。~~但需要注意的是，$Dinic$的最劣复杂度也是$O(nm^2)$，因此俄罗斯人不相信网络流算法的时间复杂度，所以你在$CF$通常是看不到网络流题的。~~ 相比传统的$EK$，$Dinic$引入了一个叫做**分层图**的概念。 在寻找增广路之前，首先先对现在的残量网络进行一遍$bfs$，同时给每个点记录一下其到$S$的距离$dis$，这个距离随便是哪个距离都可以。**注意$bfs$只能遍历残量$>0$的边**。 然后在每次$dfs$找增广路时，对于一条边$u\to v$，它可以被增广那么当且仅当$dis[v]=dis[u]+1$。这样，这个图就被这么分层了。 然后我们就可以一次$dfs$增广多条路径。 ### 当前弧优化 当前弧优化指的是，找增广路的过程中，每次遍历到原来到过的一个点，不去遍历它的每一条边，而是从上次没遍历的边开始遍历。注意每次重建分层图的时候都要还原$cur$。 ### $Capacity\ Scaling$~~玄学~~ 并不知道如何翻译。 $Capacity\ Scaling$指的是，在每次$Dinic$算法的执行过程前，先设定一个权值$val$，然后在**整个$Dinic$算法的执行过程中，只有残量$\ge val$的边才会被计算。**譬如$BFS$分层的的时候找的只能是$cap\ge val$的边，增广时亦然。 这个权值每次逐渐缩小，最后会到0，注意$=0$的时候也要跑一遍。 具体权值的设定，每次缩小的倍数完全是玄学，但能够起到相当好的优化效果。~~毕竟loj127过了88pts~~ ### $Application:$ ### $DAG\ Minimum\ Path\ Cover$ 最小路径覆盖指的是用最少的路径覆盖图中的所有顶点。**路径不可（点）相交。** $DAG$上的最小路径覆盖是可以使用多项式算法解决的。 我们把每个点拆成两个点，如果有一条$u\to v$的边，就让二分图左边的点$u_l$向右边的点$v_r$连一条边，然后$n-$二分图的最大匹配数就是最小路径覆盖数。 原因可以感性理解一下，每匹配一条边，就有两条路径被缩在一起。加上二分图上的每个点最多属于一条匹配边，与路径不相交的这个限制也契合。 ### $DAG\ Minimum\ Chain\ Cover$ $DAG$最小链覆盖的求解就是先传递闭包，再进行最小路径覆盖。感性理解的话就是通过传递闭包让原来要通过多条边才能到达的两个点直接有一条路径连接，就不会造成与其它路径相交的问题。因此这样的路径覆盖就是原图的最小链覆盖。 另外，最长反链问题可以通过$Dilworth$定理转化为最小链覆盖。可以去[这里](https://www.luogu.org/blog/teafrogsf/post-SA)看看。 ### $Eulerian\ Circuit\ in\ Hybrid\ Graph$ 本质上是一种利用度数限制建模的套路。 **** 有向图形成欧拉回路的充要条件是弱连通以及入度$=$出度。如果有无向边，我们要这样处理： 首先我们随机给无向边定向，然后得到每个点的入度和出度。如果某个点的入度与出度奇偶性不相同的话就无解了。 如果有解，我们拆点建个二分图，把出度$>$入度的点与$S$连，容量为$\frac{out-in}{2}$，入度$>$出度的点与$T$连，容量为$\frac{in-out}{2}$。然后把无向边放到二分图上（与定的方向一致），容量为$1$，意思就是这条边可以反向，并且可以改变它连的两个点的度数。 然后直接跑最大流，验证是否可以满流（即全部点都被修正）即可。 ### $Upper\&Lower\ Bound\ NF$ 分四部分写。~~因为名字实在太复杂了只能写中文了~~ ### 无源汇上下界可行流 这是一种循环流，因为没有源汇，**它的所有点都要保证流量守恒**。注意只有这种情况该流才可行。 首先，我们为了能够让流量达到下界，可以构造一个初始流。即每条边的流量在一开始先定为下界$L$。这样的网络流不一定满足流量守恒，也就是说我们接下来的目的是通过调整（给边加流量）使它流量守恒，这也就是最终的可行流。 那我们可以通过在残量网络上增广，得到一个附加流，然后附加流和初始流加在一起满足流量守恒。 也就是说，如果一个点在初始流中$in>out$，在附加流中就要$in'<out'$，那么它就应该有多余的流出量，但它在网络上的流入量并不能满足它的流出量，而我们的网络流算法又必须要求源汇，并且一定保证求出来的流流量守恒，那么就干脆给它一个源点来满足它的流入量。也就是说，我们建**虚拟源汇**（因为有源汇图是有真正源汇的）$SS,TT,SS$向这个点连一条容量为$in-out$的边。反之如果这个点$in<out$，附加流中就需要$in'>out'$，也就是它向$TT$连一条容量为$out-in$的边。之后我们只需要对这个网络求最大流，如果流满了的话，就意味着流可行。每条边实际的流量就是它的附加流量加上初始流量也就是流量下界。 ### 有源汇上下界可行流 显然源汇非常麻烦，因此我们不妨转化成无源汇的形式。 为了让源汇流量守恒，我们从$T\to S$连一条容量为$[0,+\infty]$的边，这样就把流量流回来了。然后就按照无源汇的做。 可以很发现求可行流量非常方便，就是$T\to S$这条边的流量，因为$S,T$满足流量守恒。 ### 有源汇上下界最大流 这是比较常见的。 首先我们找出一个可行流，然后我们把直接在残量网络上求$S\to T$的最大流就可以了。显然这样既保证了可行又能够增广到最大。 注意要把$T\to S$拆掉。 ### 有源汇上下界最小流 这个东西也有点意思。 首先我们找出一个可行流，然后我们的目的是撤销掉一些流量使得流仍然满足流量下界。 于是反向边流量的增加等价于正向边流量的减少，那么我们只要在残量网络上跑$T\to S$的最大流，然后用可行流$-$最大流就是最小流了。同样这也保证了合法。 注意也要拆边。 ### $Maximum\ Weighted\ Closed\ Subgraph$ 闭合子图指的是一个有向图的点集$V$，满足这个点集里每个点的后继都在这个点集中。最大权就是给每个点套上一个权值，使得选出来的闭合子图权值最大。显然一般权值是有负数的。我们怎么用网络流解决这个问题呢？ 首先我们让正权点被$S$连，容量为$val_i$，让负权点连$T$，容量为$-val_i$。然后答案就是正权点之和$-$最小割，其中闭合子图就是与$S$相连的连通块。下面是对这种方法的证明： **** 首先，最小割一定是简单割，因为你不可能去割那些正无穷的边。 其次，简单割一定对应了一个闭合子图。这个可以证充要条件： 简单割割出来的与$S$相连的集合是一个闭合子图，因为对于任意一个闭合子图中的点$G$，它的出边一定都是$+\infty$，不可能被割掉； 闭合子图对应的割是简单割，因为假设它不是简单割，那么意味着我们割掉了一条正无穷的边，而这显然是不成立的。 **** 然后我们可以算答案了： 最小割$=\sum_{x\in T,val_x\ge 0}val_x-\sum_{x\in S,val_x<0}val_x$，意思就是如果我割了一条边，那么一定意味着一个正权点变成属于$T$或一个负权点变成属于$S$。 而最大权闭合子图的权值=$\sum_{x\in S,val_x\ge 0}val_x+\sum_{x\in S,val_x<0}val_x$。~~废话~~ 那么最大权闭合子图的权值$=\sum_{x\in S,val_x\ge 0}val_x-MC+\sum_{x\in T,val_x\ge 0}val_x=$所有正权点之和$-$最小割。 并不清楚$leoly$为啥说可以不用缩$SCC$。 ### $Dual\ Graph$ 这里在未来会写有关对偶图建图的套路。 ### $Hall\ Theorem$ $Hall$定理指的是，一个二分图左右分别有$m\le n$个点，那么若它存在完备匹配，当且仅当左边**任意**$k(k\in[1,m])$个点**至少**与右边$k$个点相邻。 证明可以用反证法，因为如果某$k$个点不满足这个条件，那么这$k$个点就匹配不了。 在$OI$中，$Hall$定理通常是一种工具，具体的算法是不固定的。 ### $Output\ Ways$ 通常来说，网络流输出方案是在残量网络上进行的。 ### $Edges\ in\ Minimum\ Cut$