1、第五章 图上的算法5.15.1并查集并查集5.25.2生成树生成树5.35.3最短路最短路5.45.4强连通分量强连通分量5.55.52SAT2SAT5.65.6差分约束差分约束5.75.7二分图二分图5.85.8网络流网络流图论（GraphTheory）是数学的一个分支，它以图为研究对象。图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述事物之间的某种特定关系，其中可用点代表事物，用连接两点的线表示相应两个事物间的关系。图是由两个集合V和E组成，记为G（V，E），其中V是顶点的有穷非空集合，E是V中顶点的偶对（边或弧）的有穷集合，其中E（G）可以是空集。若E（G）为空，则图G
2、只有顶点而没有边（或弧）。通常，描绘一个图的方法是把顶点画成一个小圆圈，如果相应的顶点之间有关系，就在顶点之间画一条边（或弧）。图论涉及的问题比较多，常见的有以下几个方面：（1）并查集。（2）生成树。（3）最短路。（4）强连通分量。（5）2SAT。（6）差分约束。（7）二分图。（8）网络流。图论中的相关理论为解决现实生活中的实际问题提供了依据，分析、设计这些算法很有意义。并查集是一种树形的数据结构，其组成结构往往是森林。我们知道，森林是图的特殊形式。并查集经常用于处理不相交集合的合并及查询问题。并查集支持以下三种操作：（1）初始化：将所有集合进行初始化操作。（2）合并：合并两个集合。（3）查询
3、：查询某个节点所属的集合编号。为实现以上三种操作，我们定义int fa（farther）数组用来计算每个节点所属的集合，每一个fai代表节点i的父节点的编号。那么，所有节点组成的fa数组共同构成了一个森林，每一个森林的根的编号作为该棵树所有子树所在的集合，用find（i）表示节点i当前所处子树的根，那么，如果find（i）=find（j），则说明点i和点j此刻处在同一个集合中。初始情况下，每个节点所属集合都是该节点本身的编号，其父亲都是该节点本身，因此，初始化函数是：void init（）for（int i1；in；i）fati1；return；5.1并查集当需要查找某一个节点所属的集合时，只
4、需要从这个节点开始，不停的调用ifai向其父亲寻找，直到找到该子树满足ifai的根节点即可。int find（int i）if（ifai）return i；return find（fai）；合并两个集合，可以直接将两个集合的根进行合并，假设当前需要对点i、j 所处的集合进行合并，find（i）、find（j）代表它们所处子树的根节点，那么，只需要将 find（i）的farther更改为 find（j）或将 find（j）的 farther 改为 find（i）即可，如图 5.1 所示。图图5.1 5.1 并查集的合并操作并查集的合并操作5.1并查集int union（int i，int j）f
5、afind（i）find（j）；return O；上面的操作共同构成了并查集，但是在实际运行的时候，却有一个明显的问题：在合并的过程中，如果每次都在合并两条链，那么最终的并查集将会成为一个链式结构，每次的查询操作复杂度会退化成O（n），如图5.2所示。图图5.2 5.2 并查集可能出现的一种问题并查集可能出现的一种问题5.1并查集为避免这样问题的发生，需引入并查集find操作的一个优化：路径压缩。在查找的过程中，已经知道了该节点所在子树的根是谁，那么，在查找的过程中，将路径上所有节点的父亲都更改成这棵子树的根，在下次查找的过程中，只需要一次操作便可以找到这棵子树的根是谁，为实现它，需要稍稍修改
6、find函数。int find（int i）if（ifai）return i；return faifind（fai）；如此一来，并查集就变成了一个时间复杂度为O（kn）的数据结构，其中，n代表节点的个数，k可以认为是一个不超过5的常数。并查集在图论中用来维护节点的连通性，是一种非常高效简洁的数据结构，有着广泛的用。5.1并查集生成树是图论中的另一个问题，最常见到的是最小生成树，其定义为：对于一个无向连通图G（V，E），其中V是顶点集合，E是边的集合，对于E中每一条边（u，v），都有一个权值w（u，v）表示连接u和v的代价。我们希望找出一个无回路的E的子集T，它将G中所有的顶点连通，并且其权值之
7、和最小。生成树模型如图5.3所示。图图5.3 5.3 生成树模型生成树模型5.2生成树由于图中无回路且连通了所有的节点，其必然是一棵树，称为生成树（spanningtree）。又因为子集T是其中w（T）最小的方案，因此称子集T构成的树为图G的最小生成树。w（T）w（u，v）（u，v）属于T求最小生成树常用的算法有prim算法和kruskal算法，本书中只介绍应用较广泛、效率相对较高的kruskal算法。kruskal算法本质上是一种贪心算法，要用到并查集来维护节点之间的连通性，算法流程如下：（1）对所有边按照从小到大排序。（2）枚举每一条边（i，j），如果i与j不属于同一个连通块，则将其加入最
8、小生成树边集。（3）加入n一1条边时，最小生成树完成。算法的时间复杂度是O（mlnmm）O（mlnm）【例例5.45.4】TwoFamousCompanies。给定一个n个点、m条边的图，图上的边要么属于公司a，要么属于公司b，现在要求一个最小生成树，要求这个最小生成树上属于a公司的边恰好有k个。N50000,M100000。【算法分析算法分析】题目已经说明要求最小生成树，因此算法中必定会包含最小生成树算法，而kruskal算法的复杂度是O（mlnm）106，使用单纯的kruskal算法显然可以把数据出的更大一些，因此此题必定还会结合某复杂度在O（10）级别的算法。但本题中，数据范围并没有接近
9、10的数字，因此，考虑log级别的算法。5.2生成树首先考虑单纯对本图做最小生成树。那么会有三种情况：公司a的边k；公司a的边k；公司a的边k。如果公司a的边k，那么已经得到答案。如果公司a的边k，我们希望在最小生成树中尽量多的加入公司a的边。如果公司a的边k，我们希望在最小生成树中尽量少的加人公司a的边。在kruskal算法中，想要让某一种边尽量少的加入到最小生成树中，一种办法就是改变排序的比较方式，让它尽量向后排，反之则让它尽量靠前排。比较时，比较的是每条边的大小，因此，可以考虑如下方式：（1）如果公司a的边k，则把公司a的边都减少一定数字，使得其尽量靠前排。（2）如果公司a的边k，则把公
10、司a的边都增加一定数字，使得其尽量靠后排。以上做法以k为分界点，在分界点的两边做了不同的决定，正符合了二分算法的特点!利用二分法的思想，我们可以二分一个区间delta一r，r，每次将delta加进每一条边a中，做最小生成树，根据公司a的边的个数，决定delta抛弃左区间还是右区间，直到找到恰好使用k条边的位置。算法复杂度在原来的基础上增加一维二分复杂度，恰好满足题目要求。【程序实现程序实现】/*prob：Hdoj42535.2生成树5.2生成树5.2生成树5.2生成树最短路算法是图论中最经典、也是最常见的算法之一。其模型是在一幅图G中，找到从某个点s到另一个点t的一条路径，使得这条路径的距离之
11、和最小。最短路径又分为单源最短路径和多源最短路径。单源最短路径常用的算法有dijkstra、spfa等，多源最短路径常用的算法有floyd等，这里只简单介绍spfa算法和floyd算法。spfa算法是bellman-ford算法的一个优化，该算法简单，效率较高，程序员经常使用它。spfa的作用是对于一个起点s，求出图中其他所有节点距离它的最短路径。其基本流程是：（1）将起点加入队列中。（2）如果队列不为空，取队首元素，通过队首元素，更新与队首元素相连的所有节点距离起点的最短路径。（3）如果有节点被更新，且其不在队列中，则将其加入队列。（4）将已经处理后的当前队首元素出队。（5）重复（2）-（4
12、）过程，直到队列中不再有元素。其伪代码如下：q.push（s）；while（!q.empty（）headq.front（）；for（every edge connected head）5.3最短路 update（edge.j）；if（updated（）edge.j not in q）q.push（edge.j）；q.pop（）；spfa算法的时间复杂度没有严格的证明，一般情况下，我们认为spfa算法的时间复杂度是O（kE），k是一个常数，E是边的个数。spfa算法不仅仅可以解决单源最短路径问题，也可以解决多源最短路径问题。对于一张图，如果我们需要知道任何两个节点之间的距离，只需要枚举每一个起点
13、，对每一个起点做一次单源最短路即可。除了spfa算法，还有一种非常容易实现的O（n）复杂度的多源最短路径算法floyd，有些并非最短路径算法的问题，使用floyd算法可以很好的缩短代码量，提高编码效率。floyd算法的本质是动态规划。其核心思想是：disij=min（disikdiskj）即：从i到j的最短路等于从i到k的最短路从k到j的最短路。伪代码如下：for（int k=1；k=n；k）for（int i=1；i=n；i）5.3最短路for（int j=1；j=n；j）if（i!=k!=j）disij=min（disij,disikdiskj）；【例例5.75.7】昂贵的聘礼。给定一幅图
14、G，除了每条边上有一个距离之外，每个点上还有一个level，现要求一个从s到t的最短路，要求路径上经过的任意两个节点level之差不能超过k，求最短路径长度N100,level100。【算法分析算法分析】本题的数据范围特别小，因此直接枚举level的最小值，然后每次把level满足在level，levelk区间内的边提取出来，执行一次spfa即可，共需要执行最多100次spfa，时间复杂度是O（levelN2）。【程序实现程序实现】/*prob：Poj1062lang：c*/#includecstdio#includecstring#includealgorithm5.3最短路5.3最短路5.
15、3最短路5.3最短路5.3最短路强连通分量是图论中又一重要知识点。强连通分量的定义是：如果在图G（V，E）中，存在一个V的子集C，使得对于C中的任意一对节点（x，y）都满足从x可以到达y，我们称C是图G的一个强连通分量。另外，强连通分量是可以合并的。例如，对于图G的两个子集C1、C2，若C1和C2都是强连通分量，且它们至少有一个节点相同，则C1C2也是一个强连通分量。求图的强连通分量常用的算法是Kosaraju或Tarjan，本章介绍Tarjan算法。我们可以从某一个节点开始，对整幅图进行dfs，用dfni表示节点i是从起点开始经过几步到达，即i是处在本次dfs的第几层。用lowi表示在dfs
16、的过程中，从i之后的dfs能够到达的最小的dfn值是多少。那么，如果对于一个节点i满足：dfni=lowi说明，从i这个点可以回到它本身，i以及它在找到lowi过程中的所有点共同构成了一个强连通分量，可以合并。为了将这些节点合并，我们还需要在dfs的过程中将所有dfs到的点压入一个栈中，以便于合并时的操作。伪代码如下：tarjan（u）DFNuLowuIndex为节点u设定次序编号和Low初值Stack.push（u）将节点u压入栈中 for each（u,v）in E枚举每一条边5.4强连通分量if（v is not visted）如果节点v未被访问过 tarjan（v）继续向下找 Lowu
17、min（Lowu,Lowv）else if（v in S）如果节点v还在栈内 Lowumin（Lowu,DFNv）if（DFNuLowu）如果节点u是强连通分量的根 repeatvS.pop将v退栈，为该强连通分量中一个顶点print v until（uv）Tarjan算法的时间复杂度是O（NM），其中N是点的个数，M是边的个数。Tarjan算法可以在找到强连通分量的同时，将这些节点标记成同样的颜色，然后根据每个节点的颜色，对颜色相同的节点进行缩点，即把它们变成一个“超级点”，缩点后的点继承了原来被缩之前所有点的边，例如：有边（1，2）、（3，4），若将点（2，3）缩点，则这个点与1、4都是连
18、通的。5.4强连通分量2SAT问题的一般情况是：由N个布尔值组成的序列X，给出一系列的限制关系，例如Xa and Xb0，Xc or Xd1等，每个限制关系只对最多两个元素进行限制。2一SAT问题的目的是求一个序列X，使得其满足题目所给定的限制关系。对于2SAT问题，由于每种限制最多只对两个元素进行限制，因此，可能的限制方法有11种：X。NOT X。X AND Y。X AND NOT Y。X OR Y。X OR NOT Y。X XOR Y。X XOR NOT Y。NOT(X XOR Y)。NOT(X AND Y)。NOT(X OR Y)。为了解决 2一SAT 问题，我们对这样的问题做如下建模。
19、5.52SAT类似跳舞链一样，2SAT问题共有2N种可能的填法：第1个位置填1、第1个位置填0、第2个位置填1、第2个位置填0、第N个位置填1、第N个位置填0。我们把每一种填法当做一个点，把第i个位置填0的填法对应的点记为i，第i个位置填1的填法对应的点记为i。显然，i和i是不能同时选择的。与跳舞链不同的是，跳舞链把那些互相之间有限制的点连了起来，而2SAT问题中，是把那些有依赖的点连了起来，用有向边（X，Y）表示取了X就必须取Y，例如：X XOR Y=1那么，如果X选择了1（X），则为了满足上述等式，Y必须是0（Y），此时，对X和Y建立一条边，来描述上述的关系。（1）X：（X，X）。X必须取
20、1，那么，就必然要取X，而不能取X，因此建立一条从X到X的边，由于2SAT模型本身的定义是X和X，只能取一个，而边（X，X）限制取了X就必须得取X，因此相当于限制了X不能选0。（2）NOT X：（X，X）。原因同上。（3）X AND Y。X和Y都必须同时为1，相当于X取1且Y取1，按照方法1建图即可。（4）X AND NOT Y。X必须取1，Y必须取0，对X按照方法1，Y按照方法2建模即可。（5）X OR Y：（X，Y），（Y，X）。X和Y至少有一个为1，意味着当X或Y有一个取0的时候，另一个就必须取 1，因此建立（X，Y），（Y，X）。（6）XOR NOT Y：（X，Y），（Y，X）。X取1
21、或Y取0，那么，当X取0的时候Y就必须取 0，当 Y取 1的时候 X 就必须取1。5.52SAT（7）X XOR Y：（X，Y），（X，Y），（Y，X），（Y，X）。X和Y中只能取1个，那么，当X为1，Y就必须为0；当X为0，Y就必须为1；当Y为0，X就必须为1;当Y为1，X就必须为0。（8）X XOR NOT Y：（X，Y），（X，Y），（Y，X），（Y，X）。X取1，Y必须取1；X取0，Y必须取0。（9）NOT（X XOR Y）。该式可以简化成X XOR NOT Y，同上。（10）NOT（X AND Y）：（X，Y），（Y，X）。X和Y不能同时为1，那么，当X为1时Y必须为0，当Y为1时X
22、必须为0。（11）NOT（X OR Y）。相当于X和Y都必须是0，利用方法2处理。当图建立好之后，相当于是在图上恰好找到N个点，并且这N个点所连接的点都被选择。求解2一SAT问题有两种算法，第一种算法是暴力的做法，算法如下：枚举每一对尚未确定的Ai、Ai，任选一个，推导和其相关的所有组，如果都满足条件，则可以选择，否则选出另一个，同样的方式推导，如果依然矛盾，则必然无解。这种做法在最坏情况下的复杂度是O（NM）。另一种做法利用到了图中的对称性。试想，假设在图中发现了一个环A，那么，一旦选择了环中的某一个点，就意味着要把环中所有其他节点都选择。利用求强连通分量的算法对原图进行缩点，把所有的环都缩
23、成点，那么，选择这样个点，就意味着把这个强连通分量内的点全部选择。5.52SAT在对原图缩点后，如果存在一对节点（i，i）属干同个强连通分量内，那么意味着i和i必须同时选，显然无解。否则，采用拓扑排序的思路自底向上顺序推导，一定可以得到可行解。该算法的证明过程较为复杂，此处不进行证明。算法的流程如下：（1）构图。（2）利用强连通分量的相关算法把原图缩点，构造一个新的有向无环图。（3）判断每个点内是否存在矛盾的点（i，i），如果存在则无解。（4）对新图进行拓扑排序。（5）按照拓扑序从大到小的顺序进行选择，若此时可以选择该节点，则选择，若此时不能选择该节点，则删除。该算法的复杂度等于拓扑排序缩点的
24、复杂度，都是O（NM）。需要注意的是，第二种算法虽然复杂度低，但只能保证构造可行解，并不能保证字典序最小，因此，在需要构造一组字典序最小的解时，需要使用第一种算法。差分约束系统是一种将数学问题转化为最短路径问题的算法。一般情况下差分约束系统会给出一系列例如x一yb的式子，然后通过建图的方式将其转换成最短路径模型。例如:baic5jcak5.52SAT求ca的最大值。我们可以把a、b、c当做图G中的三个点，因为b一ai，我们可以认为a到b的距离最少是i，建立一条从a到b的长度为i的边；cbj，建立一条从b到c长度为j的边；cak，建立一条从a到c的长度为k的边。此时，三条边分别为：abibcja
25、ck图上的每一条边相当于是一个路径的传递。例如，通过边（a，b）、（b，c），从a到c则意味着c一aij。那么，每一条从s到t的边都是t一s范围的一个约束。题目中需要求c一a的最大值，实际上是求c一a的上界。对于每一条从a到c的路径，其长度都是一个上界，最小的那一个上界就是其最终的上界，即c一a的最大值。【例例5.155.15】给定n个区间，要求选一些数，使得每个区间最少包含两个数。问最少要选几个数?【算法分析算法分析】假设题目给出区间x，y中至少要选择两个数，用si来表示前i个数中共选择了多少个，那么有：sysx125.6差分约束另外，对于任何两个相邻的si、si1，必然有：si1si0以及
26、：si1si1这是一个典型的差分约束系统的式子，但是如何对这样的式子建图才能使得最短路径算法的结果满足题目要求。对于sy一sx12这样的式子，我们可以直接建立一条从x1到y长度为2的边。对于si1si0，我们一样对其建立一条从i到i1长度为0的边。对于si1si1，其符号与前两式符号不同，首先对两边同时乘以一1，得到：sisi11因此，建立一条从i1到i的边，长度为一1。对于本题，需要求的是最少选择的数字的个数，而所有的不等式都是使用大于等于来进行约束的，因此，所有从s到t的路径都对应了一种从s到t的最少选择的下界。由于本题要求最少选择的数字个数，即所有下界中的上界，因此，使用spfa求最长路
27、径，最长路径的值即为答案。【程序实现程序实现】/*prob：Poj1716lang：c*/5.6差分约束5.6差分约束5.6差分约束5.6差分约束5.6差分约束二分图又称双分图、二部图、偶图，指顶点可以分成两个不相交的集合U和V，使得在同一个集内的顶点皆无公共边的图。二分图是一种特殊的图，实际生活中有很多例子，例如男生和女生的配对，螺丝和螺帽的配对，上衣和裤子的配对等。判断一个图是否是一个二分图，当且仅当其满足以下两个条件：（1）没有长度为奇数的环。（2）点色数为2。点色数的定义是：使用若干种颜色对一幅图进行染色，要求任意两个相邻的点不能同色，最少使用的颜色个数即为点色数。二分图有一个重要的概
28、念：匹配。给定一个二分图G，在G的一个子图M中，若选定的所有边都没有公共顶点，则称M是图G的一个匹配。这些匹配中，选定了所有节点V的匹配称作完备匹配，点数最多的匹配称作最大匹配。如果二分图G的边是带权的，则选定边权之和最大的最大匹配称作最佳匹配。求最大匹配一般使用的是匈牙利算法，求最佳匹配一般使用 KM 算法，在后文中会有详细介绍。二分图作为一种特殊的图，解答的难点往往在于建立模型，一旦模型被建立，问题也就迎刃而解。【例例5.175.17】双栈排序。Tom最近在研究一个有趣的排序问题。如图5.4所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。5.7二分图图图5.4
29、 5.4 双栈排序双栈排序操作a：如果输入序列不为空，将第一个元素压入栈S1。操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列。操作c：如果输入序列不为空，将第一个元素压入栈S2。操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列。如果一个1n的排列P，可以通过一系列操作使得输出序列为1、2、（n1）、n，Tom就称P是一个“可双栈排序序列”。例如（1，3，2，4）就是一个“可双栈排序序列“”，而（2，3，4，1）不是。5.7二分图如图5.5所示，我们描述了一个将（1，3，2，4）排序的操作序列：a，c，c，b，a，d，d，b。图图5.5 5.5 一种合法的操作方式一种合法的操作方式
30、当然，这样的操作序列有可能有几个，对于上例（1，3，2，4），a，c，c，b，a，d，d，b是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。n1000。5.7二分图【算法分析算法分析】这道题目显然是有搜索的做法的，但搜索的做法显然不能得到满分。这一道看起来与二分图完全无关的题目，正解却是二分图。我们一步一步对题目的信息进行挖掘。首先考虑这样一个问题：怎样的两个数字不能在排序的过程中放进同一个栈中?在此处不能放进同一个栈代表着自始至终都不能放进同一个栈。例如：输入序列是2，3，1，4显然，没有一种操作方法能够使得2和3在排序的过程中放入同一个栈中。原因是，1是第三个出栈的
31、元素，因此，在1入栈前，2和3必然不能够出栈，而2又比3先入栈，还要先出栈。栈是一种先进后出的数据结构，如果2和3在排序的过程中进入的是同一个栈，那么出栈时，必然是3先出栈，之后才是2出栈。更普遍的，如果对于输入序列中的两个元素si、sj，如果存在k满足：（1）ijk。（2）sksisj。那么si和sj在排序的过程中必然不能进入同一个栈，证明方法同上。我们用边（i，j）来描述i和j不能够进入同一个栈，通过这样的方法建图。本题中，一共只有2个栈，那么，如果一旦在这样的图中存在一个长度为奇数的环，则说明必然无解，例如：5.7二分图（i，j）（j，k）（k，i）这三个点两两不能进入同一个栈中，那么，
32、至少需要3个以上的栈，才能够满足这个限制条件。当环的长度为5、7时一样不能用2个栈满足题目要求。在本节开始时提到，二分图的判定有一个非常重要的条件：没有长度为奇数的环。显然，本题判断是否有解，其实就是判断按照这样的建边方式，能否用一个二分图来描述这幅图。需要注意的是，当点色数为1的时候，依然可以满足题目的要求，只是仅仅使用操作a和b就可以解决题目。通过O（n）的复杂度，可以把所有有冲突的边找到并建图，剩下就是求解的过程了。题目要求的是字典序最小的序列，那么，第一个元素显然是应该使用操作a来进栈的，染色为颜色0，此时，与第一个元素有冲突的所有点都应该使用操作c来进栈，染色为颜色1，通过这些颜色为
33、1的点，又能将与它们相连的点染色为颜色0如此涕归的颜色。接下来，枚举当前最靠前的还未被染色的节点，执行上述的染色操作。如果在染色的过程中，发现某个节点既被染了颜色0，又被染了颜色1，那么，显然是产生了矛盾，该图不可能有解。如果染色已经结束，还未出现冲突，则说明原题目是有解的，此时，所有的元素进入哪一个栈已经明确，按顺序模拟即可。5.7二分图5.7二分图5.7二分图5.7二分图5.7二分图【5.8.15.8.1网络流的概念网络流的概念】1.1.网络的定义网络的定义图G（V，E）是一个简单的有向图，在图中，有两个节点s、t，其中s称作源点，t称作汇点，源点有无穷多的水流可以流出，汇点可以接收无穷多
34、的水流。图中的每一条边（i，j）有一个权值Cij，称作该条边的容量，我们把这样的图称作一个网络，记作G（V，E，C）。如图5.6所示。2.2.最大流的定义最大流的定义在网络中，单位时间内可以从源点s流出无穷多的水流，单位时间内汇点可以接收无穷多的水流，每条边最多可以接收的流量为其容量大小Cij。最大流的定义是，在最好的情况下，每单位时间可以从源点s流入多少水流到汇点t。原图中的最大流是3，如图5.7所示。图图5.6 5.6 一个网络一个网络图图5.7 5.7 最大流最大流5.8网络流【5.8.25.8.2最大流的求解方法最大流的求解方法】求最大流的方法与二分图中求最大匹配的方法很相似，都是使用
35、求增广路的方法，其区别在于：二分图中求增广路，每条边的长度都是1，网络流中求增广路，则是要求一个最大的流量。例如，在一条水流中，依次经过了4条边，这四条边的容量分别为5、4、6、2，那么，在这一条路径中，单位时间能够经过的最大水流是2，即所有边中容量最少的那一个。更普遍的，在求解最大流时，使用的是残余流量这个概念，如图5.8所示，虽然边（2，4）的容量为3，但由于已经有1的流量经过，剩余的容量只有3一12。在求解增广路的过程中，有些边的水流方向可能是错的，需要把这些水流“退回来”，需要引入反向弧的概念。如图5.9所示。反向弧通俗的理解，就是“给程序一次后悔的机会”，例如，在个网络中，从点x到点
36、v的容量是16，当前经过的流量是11，剩金的容量是5，那么，意味着从y到x此时最多可以“退”11的流量回去，因此，可以建立一条从y到x的容量为0，流量为一11的边。更普遍的，对于网络中任何一条从i到j容量为Cij的边，可以构造一条从i到i容量为0，流量为0的边，当有流量flow从I流向i时，反向边的流量flow。图图5.8 5.8 残余流量残余流量图图5.9 5.9 反向弧反向弧5.8网络流求解增广路的常用方法有：（1）宽度优先搜索。（2）深度优先搜索。（3）带标号的搜索。在网络流算法中，一般使用效率较高的第三种搜索方式，其也被称作dinic算法。求解增广路的带标号搜索算法流程如下：（1）以s
37、为根节点，对原图做一次宽度优先搜索，按照每个节点距离根节点的深度对所有节点编号并分层。（2）从s开始，使用深度优先搜索向下一层寻找节点t，在寻找的过程中记录路径上的可行流量flow即min（Cij），找到节点t后，把所有的正向边流量flow，所有的反向边流量flow。起初，对于一条边（i，j），反向边的流量为Cij，意味着不能有反向的流量从i流到i，随着从i到j的流量增加，反向边流量将逐渐减少。（3）return flow给上一层。流程2的伪代码如下：x是当前节点编号，a是当前流量大小int dfs(int x，int a)if（a0即没有流量 or xT即到达目标）5.8网络流return
38、a；返回流量给调用者 flow是当前节点可以扩展出的流量，f是临时变量 int flow0，f；for（每一条层次只比x大1的边，对应节点是y）如果水流走向y可以通到目标Tif（dfs（y，min（a，剩余流量（x，y）!0）正向边流量f；反向边流量一f；当前流量af；该节点的流量flowf；return flow；5.8网络流在网络流中有这样一个定理：当网络中找不到增广路时，网络必定已经达到最大流。因此，求解最大流的思路就是不断重复上述操作，直到再也找不到增广路。伪代码如下：build是按层次标号的过程，由于在求解最大流的过程中边的流量在变化，因此有些边所在的层次会改变当从s层次遍历不能到达t时，说明不存在增广路，可以breakwhile（build（）做一次增广路 ansdfs（0，INF）；dinic算法的时间复杂度是O（nm），对于网络流中的大部分题目已经够用。dinic算法的一个较好实现如下，请读者选择性阅读。【程序实现程序实现】struct Edge int from，to，cap，flow；Edge（int a，int b，int c，int d，）：from（a），to（b）cap（c），flow（d）；5.8网络流5.8网络流5.8网络流5.8网络流
