Goldberg-Tarjan方法
Ford-Fulkerson方法是所有增广路算法的基础，Goldberg-Tarjan方法则是基于预流的算法的基础，定义了“推送”与“重贴高度标签”两个重要操作，故也称“推送-重贴标签”方法。下面给出需要的概念与定义：
1) 预流：流网络上的预流与流非常相似，其唯一区别在于任意顶点的总流入可大于等于总流出。所以流是预流的特例，任意顶点的总流入等于总流出的预流即是合法的流。算法将通过不断的调整预流使其变为合法的最大流；
2) 超额流：给定流网络与预流，任意顶点的超额流为总流入减总流出；
3) 溢出点：除了源与汇，总流入大于总流出的顶点称为溢出点；
4) 残存网络：流网络与其上的一个预流，可以和流一样的给定一个残存网络；
5) 高度函数：给定流网络\(G=(V,E)\)的源与汇为\(s\)与\(t\)，其上有预流为\(f\)，\(f\)给定了预流残存网络\(G_f=(V,E_f)\)。如果非负整数函数\(h\)满足\(h(s)=|V|,h(t)=0\)，且对于\((u,v)\in E_f\)有\(h(u)\leq h(v)+1\)。那么认为函数\(h\)是一个合法的高度函数。算法将通过不断调整高度，用高度指导预流的调整，并维护高度为合法的高度函数；
下面给出通用预留推进方法的流程如下，规定任意顶点\(u\)的超额流值和高度为\(u.e\)与\(u.h\)：
1) 初始化任意节点\(u\)的高度，若\(u=s\)则\(u.h=|V|\)，否则\(u.h=0\)；
2) 初始化预流\(f\)，对于任意\(s\)的出边\((s,u)\)有\(f(s,u)=c(s,u)\)，其他情况\(f=0\)；
3) 若当前存在溢出点\(u\)，则当前残存网络存在\(u\)为起点的边。否则当前预流\(f\)是一个合法的流且是最大流：
3.1) 若存在\((u,v)\in E_f\)满足\(u.h=v.h+1\)，计\(A=min\{u.e,c_f(u,v)\}\)。在流网络从\(u\)到\(v\)发送\(A\)的流量，或从\(v\)到\(u\)退回\(A\)的流量(残存网络存在双向边)，称该操作为“推送”，计为\(PUSH(u,v)\)；
3.2) 若所有\((u,v)\in E_f\)满足\(u.h\leq v.h\)，调整高度\(u.h=1+min\{v.h|(u,v)\in E_f\}\)。根据高度函数的定义，这是任意高度函数当前允许的\(u\)的最大高度值，该操作在CLRS称为“重贴标签”，计为\(RELABEL(u)\)；
4) 返回步骤(3)。这里需注意到(3.1)与(3.2)是对(3)的完整划分，因为溢出点必然发出残存边，残存边两端的高度值必须符合高度的定义，这两种情况按高度进行了完整的划分；
下面通过若干的引理来同时验证算法的正确性与其代价的上界：
a) 上述流程执行过程中，任意顶点\(u\)的高度永远不降低，且每次\(RELABEL(u)\)使\(u\)高度至少+1；
上述流程显然只出现高度提升的操作，并且根据高度的定义与\(RELABEL\)操作的定义，高度至少+1。
b) 上述流程执行过程中，所有顶点\(u\)的高度\(u.h\)，永远保持为合法的高度函数；
首先考察初始高度的合法性，由于\(s\)的出边容量被加满，对于残存网络所有含\(s\)的边，其只能是\(s\)的入边\((u,s)\)，显然\(|V|=s.h>u.h=0\)符合高度定义。对于残存网络任何不含\(s\)的边\((w,v)\)， \(h(w)=h(v)=0\)满足\(h(w)\leq h(v)+1\)，所以初始高度合法。接下来任意\(RELABEL(u)\)执行后对所有\((v,u)\in E_f\)，\(u.h\)升高不影响高度合法性，对所有\((u,v)\in E_f\)，\(u.h=1+min\{v.h\}\leq 1+v.h\)符合高度定义。任意\(PUSH(u,v)\)执行后，可能使\(G_f\)失边\((u,v)\)或加边\((v,u)\)，前者剩余高度保持合法，后者满足\(u.h=v.h+1\)符合高度定义\(v.h\leq u.h+1\)。
c) 上述流程执行过程中，残存网络上永远没有源到汇的简单路径；
用反证法证明命题“给定流网络\(G\)与预流\(f\)，即给定残存网络\(G_f\)。若\(G_f\)有合法的高度函数，则\(G_f\)无源到汇的路径”。假设存在源\(v_0\)到汇\(v_k\)的\(G_f\)上的简单路径\(p=v_0v_1…v_k\)，则\(k<|V|\)，存在合法高度函数\(h\)。对\(p\)边\((v_i,v_{i+1})\)，其属于\(G_f\)，故\(h(v_i)\leq h(v_{i+1})+1\)，\(h(v_{i})-h(v_{i+1})\leq 1\)。两边对路径节点求和\(|V|-0=h(v_0)-h(v_k)=\sum_{0}^{k-1} ( h(v_{i})-h(v_{i+1}) ) \leq k\)，导致矛盾。
d) 若上述流程能够正常结束并且当前已经结束，则当前流网络上的预流是合法的流，且是最大流；
流程结束时所有顶点无超额流，此时的预流\(f\)为合法的流。由(b)所有顶点的高度在流程的任何时刻都为合法的高度函数，故在结束时也是合法的高度函数。再根据(c)此时的流\(f\)给出的残存网络\(G_f\)上无增广路，根据增广路定理\(f\)为最大流。
e) 给定流网络\(G\)，预流\(f\)，源\(s\)。若\(x\)为溢出点，则残存网络\(G_f\)存在\(x\)到\(s\)的简单路径；
设\(U\)为\(G_f\)中全体从\(x\)出发沿着简单路径可达的顶点集(包括\(x\)本身)，那么假设\(s\notin U\)。计\(U’=V-U\)，那么\(V=U\bigcup U’\)，对\(U\)所有顶点的超额流量求和有：\(\sum_{u\in U} e(u)= \sum_{u\in U}(\sum_{v\in V}f(v,u)-\sum_{v\in V}f(u,v))\)
\(=\sum_{u\in U}( (\sum_{v\in V}f(v,u)+\sum_{v\in U’}f(v,u)) – (\sum_{v\in U}f(u,v)+\sum_{v\in U’}f(u,v)) )\)
\(= \sum_{u\in U}\sum_{v\in U}f(v,u) + \sum_{u\in U}\sum_{v\in U’}f(v,u) – \sum_{u\in U}\sum_{v\in U}f(u,v) – \sum_{u\in U}\sum_{v\in U’}f(u,v) \)
\(= \sum_{u\in U}\sum_{v\in U’}f(v,u) – \sum_{u\in U}\sum_{v\in U’}f(u,v) \)
由于仅有\(s\)有负的超额流，故\(U\)所有节点都无负的超额流，但溢出点\(x\in U\)，故\(\sum_{u\in U} e(u) = \sum_{u\in U}\sum_{v\in U’}f(v,u) – \sum_{u\in U}\sum_{v\in U’}f(u,v) > 0\)，进而\(\sum_{u\in U}\sum_{v\in U’}f(v,u) > 0\)，即\(G_f\)中至少存在1条\(U\)到\(U’\)的边，这导致\(U’\)至少有1个顶点\(x\)出发可达，其可被加入\(U\)导致矛盾。
f) 若顶点\(x\)为溢出点则\(x.h\leq 2|V|-1\)，且对于上述流程的任何时刻，所有顶点高度满足该式；
由(e)在\(G_f\)存在\(x\)到\(s\)路径\(p=v_0v_1…v_k\)，高度满足\(h(v_{i})\leq h(v_{i+1})+1\)，即\(h(v_{i}) – h(v_{i+1})\leq 1\)。对\(p\)所有边求和有\(v_0.h-v_k.h\leq k\)。由于路径性质\(k\leq |V|-1\)且合法高度函数的源点高度为\(|V|\)，故整理得\(x.h\leq s.h + k=|V|+k\leq 2|V|+1\)。在上述流程开始时所有顶点的高度满足该式，每次\(RELABEL(x)\)后只有\(x\)高度改变，执行后\(x\)高度仍合法仍为溢出点，故仍满足原式，故所有顶点高度仍满足原式。每次\(PUSH\)后所有顶点高度不变且所有顶点高度合法，故所有顶点高度仍满足原式。故上述流程在任何时刻所有顶点的高度满足原式。
g) 上述流程执行过程中，\(RELABEL\)的总执行次数小于\(2|V|^2\)；
利用(f)与(a)可知每个顶点至多执行\(2|V|-1\)次\(RELABEL\)，那么对所有顶点至多执行共\(2|V|^2-|V| < 2|V|^2\)次。
h) 上述流程执行过程中，饱和推送指\(PUSH(u,v)\)后\(c_f(u,v)=0\)，饱和推送总次数小于\(2|V||E|\)；
首先明确对所有顶点对\((u,v)\)，在上述整个流程中能被执行\(PUSH\)的顶点对至多有\(2|E|\)对，因为残存网络至多有原网络2倍的边。接下来分析同一顶点在上述流程中执行饱和推送的总次数界，对任意两顶点\(u,v\)，若从\(u\)到\(v\)能饱和推送，则\(v.h=u.h-1\)，执行后有\(c_f(u,v)=0\)。若接下来再次从\(u\)到\(v\)执行饱和推送，那么必须预先恢复\(c_f(u,v)>0\)，其唯一途径是先执行\(PUSH(v,u)\)，但\(PUSH(v,u)\)有前提\(v.h=u.h+1\)，即高度需+2。由(f)从\(u\)到\(v\)共执行至多\(|V|\)次饱和推送。所以对于整个流程至多执行\(2|V||E|\)次饱和推送。
i) 上述流程执行过程中，非饱和推送指\(PUSH(u,v)\)后\(c_f(u,v)>0\)，非饱和推送总次数小于\(4|V|^2(|V|+|E|)\)；
在该步骤引入摊还分析方法，定义势能函数\(\Phi\)为当前所有溢出顶点的高度总和，上述流程在刚初始化后\(\Phi=0\)。对于任意顶点\(u\)，根据(f)单次的\(RELABEL(u)\)后\(\Phi\)的增量少于\(2|V|\)，其饱和推送\(PUSH(u,v)\)不使任何节点高度变化，但可能使\(v\)从非溢出点变为溢出点，根据(f)其高度至多为\(2|V|-1\)，所以\(\Phi\)的增量少于\(2|V|\)。下面证明单次非饱和推送使\(\Phi\)至少降低1，首先注意到任意非饱和推送\(PUSH(u,v)\)结束后，所有顶点高度不变，\(u\)必从溢出点变为非溢出点，这使\(\Phi\)降低\(u.h\)。而\(v\)从不溢出变为溢出能为\(\Phi\)带来最大程度的增加。综上\(\Phi\)至少降低\(u.h-v.h\)，由于这两个值本身在执行前后不变，在不饱和推送执行前有\(u.h-v.h=1\)，故\(\Phi\)至少降低1。最后汇总这三种运算，根据\(\Phi\)的定义在上述流程中永远保持\(\Phi\geq 0\)。整个流程中\(RELABEL\)或饱和\(PUSH\)贡献的势能总和，结合(g)(h)其有上限\(2|V|(2|V|^2+2|V||E|)=4|V|^2(|V|+|E|)\)，那么整个流程中的每次非饱和\(PUSH\)至少使\(\Phi\)降低1，但总体又不能将\(\Phi\)降到0以下，故非饱和\(PUSH\)次数有上限\(4|V|^2(|V|+|E|)\)。
结论：Goldberg-Tarjan方法是正确的，且其步骤(3)的总执行次数有上界\(O(|E||V|^2)\)；
由引理(g)(h)(i)整个流程\(PUSH\)与\(RELABEL\)总数有上限\(O(|E||V|^2)\)，再根据引理(d)结束时结果正确。
前置重贴标签算法
Goldberg-Tarjan方法不容易直接转化为代价\(O(|E||V|^2)\)以下的算法，这里讨论一种相对高效的实现称为前置重贴标签算法。Goldberg-Tarjan方法每次都在当前任选1个溢出点执行\(PUSH\)或\(RELABEL\)，倘若更具策略的选择溢出点，代价将优于\(O(|E||V|^2)\)，前置重贴标签算法的代价为\(O(|V|^3)\)。下面定义相关数据结构与并给出算法流程：
j) \(LL\)链表：在流网络初始化后，将所有\(V-\{s,t\}\)顶点组织为链表\(LL\)，链表节点次序被确定；
k) \(ll[u]\)链表：对于\(LL\)中的节点\(u\)，将\(\{ v | (u,v)\in E,(v,u)\in E \}\)组织为链表，该链表的意义是\(u\)在残存网络上的所有可能邻接点，为方便讨论将该链表计为\(ll[u]\)，其节点次序同样在初始化后立即确定；
l) \(llcurrent[u]\)字典：下文中的\(discharge(u)\)运算需要“遍历或部分的遍历”上述\(ll\)中的链表，\(llcurrent[u]\)用于指示遍历起始位置，其在流网络初始化后，立即被初始化为\(llcurrent[u]=ll[u].head\)；
m) \(discharge(u)\)运算：通过连续执行\(PUSH,RELABEL\)将溢出点\(u\)转为非溢出顶点，其流程如下。
1. 初始时设变量\(v=llcurent[u]\)；
2. 开始执行循环，循环条件由下面几种情况给出；
3a. 若\(v\neq None\)，\(c_f(u,v)>0\)且\(h(u)=h(v)+1\)。执行\(PUSH(u,v)\)，执行后若\(u\)不再溢出，则\(discharge(u)\)结束。否则回到(2)。注意每次\(discharge\)对\(llcurrent[u]\)的改变需“保存”下来；
3b. 若\(v\neq None\)，\(c_f(u,v)=0\)或\(h(u)\neq h(v)+1\)。仅更新\(llcurrent[u]=v.next\)，并回到(2)；
3c. 若\(v=None\)，即链表末尾空指针，执行\(RELABEL(u)\)并恢复\(llcurrent[u]=ll[u].head\)，并回到(2)；
n) \(frontToRelabel\)算法主体：在\(LL\)遍历的执行\(discharge\)最终求得最大流，流程如下。
1. 初始时设变量\(u=LL.head\)；
2. 开始执行循环，循环条件由下面几种情况给出，直到\(u\)等于链表末尾(\(u=None\))算法结束；
3a. 执行\(discharge(u)\)后若\(u.h\)不变，则更新\(u\)为其在\(LL\)的后继，即\(u = u.next\)，回到(2)；
3b. 执行\(discharge(u)\)后若\(u.h\)改变，则将\(u\)移动到\(LL\)的表头，然后更新\(u = u.next\)，回到(2)；
接下来通过若干的概念与引理来验证上述算法的正确性与时间复杂度：
o) 许可边：若\(c_f(u,v)>0\)并且\(h(u)=h(v)+1\)，则称\((u,v)\)为许可边；
p) 许可网络：将全体许可边计为\(E_{f,h}\)，则称\(G_{f,h}=(V,E_{f,h})\)为许可网络；
q) 许可网络的性质：许可网络是有向无环图；
假设存在环路，环路上的边都是许可边，那么沿着环路对节点高度差求和，将立即推出矛盾。
r) \(PUSH(u,v)\)执行后不产生新许可边，但可能使\((u,v)\)变为非许可边；
执行后可能有\(c_f(u,v)=0\)，即许可边\((u,v)\)消失。一定有\(c_f(v,u)>0\)，但\(u.h=v.h+1\)，\((v,u)\)不能为许可边。
s) \(RELABEL(u)\)执行后\(u\)有至少1条许可出边，但此时\(u\)无许可入边；
根据定义\(RELABEL\)执行后，\(u\)与其在\(G_f\)中高度最低的邻接点构成许可边。然后假设执行后存在许可边\((v,u)\)，那么此时\(v.h=u.h+1\)，由上述引理(a)可得在执行前\(v.h>u.h+1\)，但由高度函数的定义若\((v,u)\)存在于\(G_f\)中，合法的高度函数必满足\(h(v)\leq h(u)+1\)，又由于引理(b)高度函数永远是合法的，所以假设不成立，在\(RELABEL(u)\)执行后一定不存在到达\(u\)的许可边。
t) \(discharge\)的正确性：运算\(discharge(u)\)在执行\(PUSH\)与\(RELABEL\)时，\(u\)满足相应前提条件；
利用类似循环不变式的思路验证这点：
i) 其中\(PUSH\)操作显然满足前提条件。需证明的是执行\(RELABEL(u)\)时，\(u\)在残存网络的所有出边都不是许可边；
ii) 容易发现执行\(discharge(u)\)时，如果是从\(ll[u].head\)开始遍历与执行\(PUSH\)，那么如果最后到达链表末尾且此时\(u\)仍然是溢出点，那显然此时\(u\)所有许可出边都被\(PUSH\)运算“破坏”，即符合\(RELABEL(u)\)的前提条件；
iii) 考虑一般化情况，在遍历与执行\(PUSH\)时，到达链表末尾前\(u\)已不再是溢出点，这意味本次\(discharge(u)\)会退出，那么之后如果再执行\(discharge(u)\)，则其会从“上次结束位置”继续遍历链表。在这种情况下，两次\(discharge(u)\)仅间隔对若干其他顶点(统一计为\(w\))的若干次\(discharge(w)\)，这些\(discharge(w)\)在执行前，\(u\)到“上次结束位置”之前的全部顶点都没有许可边直达，需要验证在这些\(discharge(w)\)在执行后，\(u\)到“上次结束位置”之前的全部顶点仍然保持没有许可边直达；
iv) 在这些\(discharge(w)\)中，根据(r)可知其中的\(PUSH\)不会创建新的许可边，不会导致新增\(u\)到“上次结束位置”之前顶点的许可边，根据(s)可知其中的\(RELABEL(w)\)结束后不会导致新增到达\(w\)的许可边，至于是否新增\(w\)发出的许可边，由于\(w\neq u\)，其都不可能是\(u\)到“上次结束位置”之前顶点的许可边。这个讨论可以推广到任意次数的“间隔”，所以命题成立。
u) \(frontToRelabel\)的正确性：在(n)每轮步骤(3)的结束时刻，此时刻的\(LL\)符合此时刻的许可网络顶点的拓扑序；
利用类似循环不变式的思路验证这一点：
i) 在预流与上述数据结构初始化完成的时刻，当前的许可网络没有许可边，故\(LL\)没有从后向前的边，符合拓扑排序；
ii) 设之前(n)中的步骤(3)维持了拓扑排序，本轮的\(discharge(u)\)中，根据(r)所有\(PUSH\)只可能减少许可网络中的边，那么其必然不破坏拓扑序。而\(RELABEL(u)\)的执行只能够新增或删去当前许可网络中\(u\)的出边入边，但由于(s)执行后\(u\)没有许可入边，那么此时将\(u\)移动到\(LL\)表头，必然可以使\(LL\)继续符合拓扑序的要求；
v) \(frontToRelabel\)的正确性：在(n)每轮步骤(3)的开始时刻，此时刻的\(u\)在此时刻的\(LL\)前方的所有顶点不溢出；
利用类似循环不变式的思路验证这一点：
i) 假设在以\(u\)开始的(n)的某轮步骤(3)刚刚结束，\(u\)与其前方顶点都不溢出，其后继\(u’=u.next\)将作为\(u\)开始当前新一轮步骤(3)；
ii) 新一轮步骤(3)中，其只含一次\(discharge(u’)\)，若其中仅含\(PUSH\)运算，根据(u)提供的拓扑序性质，其\(PUSH\)运算都不会是\(PUSH(u’,v)\)，其中\(v\)为任意\(u’\)前方的顶点，即\(PUSH\)不会使任何\(u’\)前方顶点流量增加，\(discharge(u’)\)结束后\(LL\)顶点次序不变，显然\(u’\)与其前方顶点都不再溢出。若其中还包含了\(RELABEL\)运算，那么在该次\(discharge\)后，\(u’\)马上被设置为\(LL\)表头，那么\(u’\)不存在前方顶点，\(u’\)必然不再溢出。
iii) 利用(ii)的递推关系可得结论如下，以\(u\)开始的(n)的步骤(3)结束时，\(u\)与其前方顶点都不溢出。
w) \(frontToRelabel\)的正确性：在(n)退出时，\(LL\)所有顶点都不是溢出点；
(n)退出说明最后次(n)的步骤(3)发生在当前\(LL\)最末顶点，由(v)此时刻的\(LL\)的最末顶点与其之前顶点都不溢出；
x) \(frontToRelabel\)的正确性：在(n)退出时，当前预流为最大流；
可发现上述步骤确实是Goldberg-Tarjan方法的实现，其就是连续的对符合要求的顶点执行\(PUSH\)或\(RELABEL\)，一直到流程(n)退出时，根据(w)当前\(LL\)无溢出点，进而流网络上无溢出点，那么达到了Goldberg-Tarjan方法的停止条件，根据(d)当前预流为最大流。
y) \(frontToRelabel\)的代价：(n)中步骤(3)的总次数有上界\(O(|V|^3)\)；
根据(g)算法过程中至多包含\(O(|V|^2)\)次的\(RELABEL\)调用，相邻的两次\(RELABEL\)调用之间，至多间隔\(|V|\)次的\(discharge\)调用，其一定不能多于这个数字，否则其早已遍历到\(LL\)尾部。这样就得到了\(discharge\)次数的一个上界\(O(|V|^3)\)，由于上述(n)的每次步骤(3)必须发生1次\(discharge\)调用，所以上述(n)的步骤(3)的总次数有上界\(O(|V|^3)\)。
z) \(frontToRelabel\)的代价：(n)中步骤(3)所有\(discharge\)的总代价有上界\(O(|V|^3)\)，整体算法代价为\(O(|V|^3)\)；
i) 由(a)(f)一个顶点至多有\(O(|V|)\)次\(RELABEL\)。设\(u\)为任意顶点，分析所有\(discharge(u)\)运算中\(ll[u]\)链表节点向\(next\)指针前进的次数上界，若次数大于\(O(|V|)\cdot ll[u].length \)，\(ll[u]\)必有大于\(O(|V|)\)次前进到末尾，即有大于\(O(|V|)\)次\(RELABEL(u)\)，导致矛盾。故每个顶点\(u\)在\(ll[u]\)的前进次数有上界\(O(|V|)\cdot ll[u].length \)。所有\(ll\)链表可看作\(E’=\{ (u,v),(v,u) | (u,v)\in E \}\)与\(V\)构成的图，该图显然满足\(|E’|\leq 2|E|\)，其任意顶点\(w\)的出度满足\(deg(w)=ll[w].length\)，即\(O(|V|)\cdot ll[u].length = O(|V|)\cdot deg(u)\)，由握手定理\(\sum_{v\in V} O(|V|)\cdot deg(v)= O(|V||E’|)\)，所以\(O(|V||E|)\)是所有\(discharge\)运算中总的链表前进次数的一个上界；
ii) 所有\(discharge\)运算中的\(RELABEL\)的总次数根据(g)，其有上界\(O(|V|^2)\)，如果顶点\(w\)执行\(RELABEL(w)\)是通过遍历的方式找到最小高度邻接点的，那么所有\(discharge\)中的\(RELABEL\)的总代价有一个上界\(O(|V|^3)\)；
iii) 所有\(discharge\)运算中，每1次饱和\(PUSH\)后都有1次链表前进，所以饱和\(PUSH\)的总代价为\(O(VE)\)。而非饱和\(PUSH\)在每次\(discharge\)只能发生1次，所以非饱和\(PUSH\)的总次数显然有一个\(O(|V|^3)\)的上界。单次\(PUSH\)运算本身容易找到\(O(1)\)的实现；
综上所有\(discharge\)产生的总代价有上界\(O(|V|^3)\)。再根据(y)所有(n)的步骤(3)被执行\(O(|V|^3)\)次，根据步骤细节，所有该步骤的总代价除去\(discharge\)的总代价为\(O(|V|^3)\)，加上所有\(discharge\)的总代价，算法总代价为\(O(|V|^3)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | class LLNode: def __init__(self,key): self.key = key self.value = None self.next = None class NetworkFlow: def __init__(self,s,t): self.s = s self.t = t self.c = {} self.f = {} self.cf = {} def add_edge(self,u,v,c): if c <= 0 : return self.c.setdefault(u,{}) self.c.setdefault(v,{}) self.c[u][v] = c self.c[v][u] = 0 self.cf.setdefault(u,{}) self.cf.setdefault(v,{}) self.cf[u][v] = c self.cf[v][u] = 0 self.f.setdefault(u,{}) self.f.setdefault(v,{}) self.f[u][v] = 0 self.f[v][u] = 0 self.e = {} self.h = {} self.ll = None self.ll_current = {} def make_preflow(self): s = self.s for u in self.c: self.e[u] = 0 self.h[u] = 0 self.h[s] = len(self.c) for u in self.c[s]: if self.c[s][u] > 0: self.f[s][u] = self.c[s][u] self.cf[u][s] = self.c[s][u] self.e[u] = self.c[s][u] def make_residual_ll(self): self.ll = None self.ll_current = {} residual_adj = {} for u in self.c: for v in self.c[u]: if not u in residual_adj: residual_adj[u] = set() if not v in residual_adj: residual_adj[v] = set() residual_adj[u].add(v) residual_adj[v].add(u) curr1 = None for u in residual_adj: if u not in (self.s,self.t): if not curr1: self.ll = LLNode(u) curr1 = self.ll else: curr1.next = LLNode(u) curr1 = curr1.next curr2 = None for v in residual_adj[u]: if not curr2: curr1.value = LLNode(v) self.ll_current[curr1] = curr1.value curr2 = curr1.value else: curr2.next = LLNode(v) curr2 = curr2.next def push(self,u,v): d = min(self.e[u],self.cf[u][v]) if self.c[u][v] > 0: self.f[u][v] += d self.cf[u][v] -= d self.cf[v][u] += d else: self.f[v][u] -= d self.cf[v][u] += d self.cf[u][v] -= d self.e[u] -= d self.e[v] += d def relabel(self,u): min_h = float('inf') for v in self.cf[u]: if self.cf[u][v] > 0: min_h = min(min_h,self.h[v]) self.h[u] = min_h + 1 def discharge(self,node): u = node.key while self.e[u] > 0: v = self.ll_current[node].key if self.ll_current[node] else None if not v: self.relabel(u) self.ll_current[node] = node.value elif self.cf[u][v]>0 and self.h[u]==self.h[v]+1: self.push(u,v) else: self.ll_current[node] = self.ll_current[node].next def front_to_relabel(self): self.make_preflow() self.make_residual_ll() prev = None curr = self.ll while curr: old_h = self.h[curr.key] self.discharge(curr) new_h = self.h[curr.key] if new_h > old_h: if prev: prev.next = curr.next curr.next = self.ll self.ll = curr prev = curr curr = curr.next def max_flow_value(self): self.front_to_relabel() val = 0 for v in self.c[self.s]: val += self.f[self.s][v] return val |