一、实验目的与要求

1、实验目的：

（1）掌握最大流算法思想。
（2）学会用最大流算法求解应用问题。

2、实验亮点：

（1）正确构建了流网络，并详细分析了流网络的结果
（2）给出了流网络与问题解的关系
（3）使用多种方法正确计算了给定网络的最大流
（4）对多种算法实现过程中必要定理进行了严谨的证明

二、实验内容与方法

使用最大流解决论文评审问题：
（1）有m篇论文和n个评审，每篇论文需要安排a个评审，每个评审最多评b篇论文。请设计一个论文分配方案。
（2）要求应用最大流解决上述问题，画出m=10，n=3的流网络图并解释说明流网络图与论文评审问题的关系。
（3）编程实现所设计算法，计算a和b取不同值情况下的分配方案，如果没有可行方案则输出无解。

三、实验步骤与过程

（一）设计流网络

要想利用网络流解决问题，第一步当然是构建流网络。为了让流网络结构更加清晰，我采用了层次的概念对流网络进行构建。下图为构建出的网络流结果，其中，省略了一些重复的节点。

根据题意，可以构建出如上流网络。其中，流网络共分四层。第一层只有源点，第四层只有汇点。中间第二层表示各个评审，第三层表示各个待评审的论文。
源点→评审： 源点分别指向各个评审节点且容量都为每个评审的最大评审论文数。由于需要对各个论文进行评审，所以源点与每个评审间存在有向边。又因为每个评审最多可以评审b篇论文，因此，从源点到评审节点的最大流量为b。

评审→论文： 对于每个已经分配的评审，评审需要评阅论文，因此存在由评审到论文的有向边。又因为对于每个评审，其评阅论文的状态只有0或1即表示未评阅或已评阅。因此从评审到论文的有向边的最大流量为1。

论文→汇点： 完成论文的评阅后将流网络汇入汇点即可。又因为，每个论文至少由a名评审进行评阅，则从论文节点到汇点有最大容量为a的有向边。当$do{c}_1$到汇点的容量为x时，表示论文$do{c}_1$被x个评审评阅了。

下面以$m=10,n=3$（10篇论文，3位评审）时构建流网络为例，展示构建的完整流网络：

网络流说明与上方说明相同，此处不赘述。

（二）流网络中最大流与论文评审问题解的关系

首先，我们知道，流网络最大流下各边的流量就是一组值班问题的解：

1. 当流网络流入汇点总量不为论文数与每篇论文需要评审数的积（m×a）时，说明有部分论文没有被规定数量（a）的评审评阅，此次论文评审问题无解；

2. 当流网络流入汇点总量为论文数与每篇论文需要评审数的积（m×a）时，最大流为论文数与每篇论文需要评审数的积（m×a），此次论文评审问题有解。
   此时关键路径【评审→论文】中某条边的流量不为 0，说明这条边被选中，即出发点评审对终点论文进行了评阅。

第一层与第二层之间的最大容量保证了每位评审的最大论文评阅数，第二层与第三层间的边表示了评审与论文的关系，即是否评阅。第三层与汇点间的最大容量限制表示了每个论文需要评审的数量。

显然，如果这个问题有解，即每篇论文都有a位评审进行评阅，那么从论文层到汇点间边的流量必为最大容量限制a。此时，最后一层与第一层间所有路径容量必全部流满，则此时流网络必为最大流，即论文评审问题的解一定对应流网络中的最大流情况。且论文评审问题是否有解的依据是最大流是否大于论文数与每篇论文需要评审数的积（m×a）。

（三）最大流的计算

经过上述流网络的分析与构建，论文评审问题已经转化为求给定流网络的最大流问题。对于最大流的求解有很多种方式，本次实验将介绍Edmonds-Karp 算法改进后的 Dinic 算法。
接下来，将介绍 Edmonds-Karp 算法以及该算法涉及的关键定理，并介绍 Dinic 算法以及具体的Dinic 算法的实现方法。

1、Edmonds-Karp 算法

（1）算法思想：

因为所有流量都将从源点 s 出发，经过中间点后最终汇至汇点 t。因此最大流的网络可以拆分成一系列增广路的集合。其中，每条增广路的流量就是当前增广路上所有边的容量限制的最小值。因此可以通过不断搜索增广路径，并消去增广过程中产生的这条增广路径所消耗的流量，并不断更新流量完成最大流问题的求解。

由于增广路的搜索需要一定的顺序，不同的顺序会导致不同的结果。因此可能会因为搜索顺序不合适导致最大流求解错误。因此，可以引入残留网络，完成对错误搜索增广路产生的流量退回。
在残留网络中对每一条边增加一条反向边，其容量与原边相同，流量为原边最大限制容量与原边已使用流量之差。

如上图，不引入残留网络时可能先找到两条通路$(A,A1,T)$与$(A,A2,T)$，这将导致流经后面 B1 时已经流量满，而无法连接节点造成最大流求解错误。引入残留网络后就可以将$(A,A1,T)$这条通路给 B，最终将得到正确的最大流结果。

（2）算法关键定理及其证明：

①增广路定理：
残留网络中任何一条从 s 到 t 的有向通路都对应原图中一条增广路。只需求解出该道路中所有残量的最小值 $d_{min}$，并把所有对应边流量增加$d_{min}$即可，这个过程被称为增广。显然，网络流中的流量可以增大，当且仅当当前网络中存在增广路。因此当残留网络中不存在增广路，则当前流即为最大流。这就是著名的增广路定理，它介绍了增广路解决最大流的思路，Edmonds-Karp算法和 Dinic 算法都是基于增广路方法的具体实现。

②证明增广路径长度递增：
不妨设 $p$为第一次 BFS找到的增广路，则 $p$ 必为残留网络$(s,t)$中最短路径。在进行增广后，$p$ 上关键边$(u,v)$将在残留网络中删去并增加反向边$(v,u)$。设第一次找到的增广路径是 $p=(s\to u\to v\to t)$，关键边为$(u,v)$。此时进行增广操作后，将从残留网络中删去正向边$(u,v)$，并增加反向边$(v,u)$。
为了证明增广路径长度递增，我们不妨假设下一次 BFS 搜索出现了长度更短的路径 $p^{\prime }$，则一定出现反向边$(v,u)，p^{\prime }=(s\to v\to u\to t)$。而 BFS 性质保证第一次搜索中 $dis(s,u)$与 $dis(v,t)$都是最短的，此时有
$$dis(s,t)=dis(s,u)+dis(v,t)+1$$
若出现了更短的边，则有
$$|p^{\prime }|=di{s}^{\prime }(s,v)+di{s}^{\prime }(u,t)+1<|p|$$
而
$$dis(s,v)\le di{s}^{\prime }(s,v),dis(u,t)\le di{s}^{\prime }(u,t)$$
与假设矛盾，因此不存在长度更短的路径$p^{\prime }$，即BFS 找到的增广路径长度是递增的。

③证明Edmonds-Karp算法迭代具有有穷上界
对于任一残留网络，在沿任一条增广路径增加流后，处于该条路径上所有关键边都将从残留网络中消失。并且任意一条增广路上都至少存在一条关键边。
因此，只需证明对于|E|中的每条边来说，其成为关键边的次数是有穷的并且为定值。此处先给出结论如下：
$|E|$中的每条边成为关键边的次数最多为$\frac{|V|}{2}$次

接下来给出证明：
不妨设 u 和 v 为集合 V 中的两个节点，且这两个节点由 E 中的一条有向边连通。由于增广路径都是最短路径，因此当边$(u,v)$第一次成为关键边时，此时有：
$${\delta }_f(s,v)={\delta }_f(s,u)+1$$
在对流进行增加后，边$(u,v)$将被从残留网络中删除。并且，以后也不会重新出现，在另一条增广路径上，直到从 $u$ 到 $v$ 的网络流减小后为止，并且只有当$(u,v)$出现在增广路径上时，这种情况才会发生。如果当这一事件发生时 $f^{\prime }$是 $G$ 的流，则有
$${\delta }_f^{\prime }(s,u)={\delta }_f^{\prime }(s,v)+1$$
依②中证明，有：
$${\delta }_f(s,v)\le {\delta }_f^{\prime }(s,v)$$
联立得：
$${\delta }_f^{\prime }(s,u)={\delta }_f^{\prime }(s,v)+1\ge {\delta }_f(s,v)+1={\delta }_f(s,u)+2$$

因此，从边$(u,v)$成为关键边到下一次再成为关键边，从源点 $s$ 到节点 $u$ 的距离至少增加两个单位，而从源点 $s$ 到节点 $u$ 的最初距离至少为0，从 $s$ 到 $u$ 的最短路径上的中间节点不可能包括节点 $s$、$u$ 或者 $t$（因为边$(u,v)$处于一条增广路径上意味着 $u$ 与 $t$ 不同）。因此，一直到节点 $u$ 成为不可达的节点前，其距离最多为$|V|-2$。因此，在边$(u,v)$第一次成为关键边时，它还可以至多再成为$\frac{|V|-2}{2}=\frac{|V|}{2}-1$ 次关键边，即边$(u,v)$成为关键边的总次数为$\frac{|V|}{2}$。由于一共有O(E)对节点可以在一个残留网络中有边彼此连接，因此Edmonds-Karp算法执行的全部过程中，关键边的总数为 $O(VE)$。每条路径至少有一条关键边，原命题得证。

在使用 BFS 寻找增广路径时，每次迭代在$O(E)$时间实现，Edmonds-Karp算法的时间复杂度因此为$O(V{E}^2)$。

2、Dinic 算法

（1）算法思想

Dinic 算法的思想也是分阶段地在层次网络中进行增广。它与 EK 算法的不同之处在于：Edmonds-Karp 算法每个阶段执行完一次 BFS 增广后，需要重新 BFS 从源点开始寻找另一条增广路；而 Dinic 中，只需一次 DFS 过程就可以实现多次增广。

不同于普通的 DFS，Dinic 算法的 DFS 并不是存在可行边就递归，还需要一层一层的进行，所以除了残留网络，Dinic 算法还需要层网络，即给节点定义一个层次，每个顶点的层次为当前顶点到达源点的最短距离。实际上该步操作与 BFS 寻找的最短路径相似，保证了每次 DFS 找到的增广路径的长度是相同的，同时保证了每次更新残留网络后，下一次找到的增广路径的长度必定是递增的，确保了算法的有穷性。

在基于生成的数据建立流网络时，就已经建立好了层次，因此本次实验中流网络一定能够给图分层，不会出现类似下图的的不能分层的网络。

（2）算法流程：

①用 BFS 建立分层图，注意分层图是以当前残留网络为基础建立的，所以要重复建立分层图；
②用 DFS 的方法寻找一条由源点到汇点的路径，获得这条路径的流量 $V_a$（路径上残量最小的边的残量）根据这条路径修改整个图，将所经之处正向边流量减少$V_a$，反向边流量增加$V_a$，注意 $V_a$是非负数；
③重复步骤 2，直到 DFS 找不到新的路径；重复步骤 1，直到图无法分层。

（3）算法实现与伪代码：

①bfs对顶点进行标号

②dfs在层次图中寻找增广

③调用Dinic算法求解最大流

（4）时间复杂度分析：

不妨设残留网络中顶点数为 $V$，边数为 $E$。
①BFS 建立层网络，耗时$O(E)$（与 EK 算法中 BFS 时间消耗一致）；
②一次 DFS 中搜索出来的增广路径也存在关键边，且关键边的个数为$O(E)$，即一次 DFS 可能搜索出$O(E)$条增广路径，对残留网络进行修改需要$O(V)$，所以一次 DFS 时间消耗为$O(VE)$。
③与 EK 算法相似，Dinic 算法存在层网络限制每次 DFS 找到的增广路径长度递增，且最大长度为$O(V)$。综上，Dinic 算法的时间复杂度为
$$O(V)\times (O(E)+O(V^{2}E))=O(V^{2}E)$$

（四）求解具体分配方案：

对于本题，存在$n,m,a,b$ 共4个变量，为讨论$a,b$间关系，不妨让$m=10,n=3$，即在有10篇论文和3个评审的情况下，讨论在不同的论文所需评审数$(a)$和不同评审最大评阅论文数$(b)$下的论文分配方案

a	b	最大流	时间消耗	是否有解
1	20	10	0.0047ms	有解
2	15	20	0.0047ms	有解
3	10	30	0.004ms	有解
4	5	15	0.0034ms	无解
5	1	3	0.0032ms	无解

可以看到，对于一些不同a，b值下的有无解情况如上。此外，我又生成了大量数据，对不同n,m,a,b的值，发现存在如下规律
论文分配有解当且仅当$n\times b\ge m\times a$
通过分析，可以给出证明如下，对于此网络流，从源点发出的流量为$V_s=bn$，而有解的条件为最大流大于$V_t=am$，又因为流网络不损失流，因此当有解时则有$V_s\ge V_t$，即$n\times b\ge m\times a$。

四、实验结论或体会

1. 日常生活中一些排班问题，分配问题，以及有先后关系的选课问题都可以通过网络流的方式进行解决
2. 网络流问题解决过程中会遇到很多专有名词，了解这些名词是解决网络流问题的先决条件
3. 可以使用有多种不同思路的算法求解最大流问题。这些算法的效率也不仅相同，应该分不同情况进行解决
4. 最大流求解中的定理证明环环相扣，需要具备比较高的数学知识才能完成证明

五、思考

上面提及的两种算法均为增广路算法，即按照增广路径不断压入少量的流量，直到满流，而预流推进算法则是一次性将巨额流量压入网络，如果能够流就让他流，即将流量转到下一个节点，否则就溢出，不管溢出的部分。

1、算法主要思想

预流推进算法通过对单个结点的更新操作，直到没有结点需要更新来求解最大流。
算法过程维护的流函数不一定保持流守恒性，对于一个结点，我们允许进入结点的流超过流出结点的流，超过的部分被称为结点 u ( u ∈ V − { s , t } ) u(u∈V-\{s,t\}) u(u∈V−{ s,t})的超额流$e(u)$：
$$e(u)=\sum _{(x,u)\in E}f(x,u)-\sum _{(u,y)\in E}f(u,y)$$

若$e(u)>0$，称节点$u$溢出。

预流推进算法维护每个结点的高度$h(u)$，并且规定溢出的结点$u$如果要推送超额流，只能向高度小于$u$的结点推送；如果$u$没有相邻的高度小于$u$的结点，就修改$u$的高度（重贴标签）。

2、算法实现：

预流推进算法的实现基于以下几个部分：

①高度函数
准确地说，预流推进维护以下的一个映射$h:V\to N$:
$$h(s)=|V|,h(t)=0$$
$$\forall (u,v)\in E_f,h(u)\le h(v)+1$$
称$h$是残存网络$G_f=(V_f,E_f)$的高度函数。
引入定理：设$G_f$上的高度函数为$h$，对于任意两个结点$u,v\in V$，如果$h(u)>h(v)+1$，则$(u,v)$不是$G_f$中的边。
算法只会在$h(u)=h(v)+1$的边执行推送。

②推送
适用条件：结点u溢出，且存在结点v，满足：
$$(u,v)\in E_f,c(u,v)-f(u,v)>0,h(u)=h(v)+1$$
则 push 操作适用于$(u,v)$
于是，我们尽可能将超额流从$u$推送到$v$，推送过程中我们只关心超额流和$c(u,v)-f(u,v)$的最小值，不关心$v$是否溢出。

如果$(u,v)$在推送完之后满流，将其从残存网络中删除。

③重贴标签
适用条件：如果结点$u$溢出，且$\forall (u,v)\in E_f,h(u)\le h(v)$ ，则重贴标签操作适用于$u$。则将$h(u)$更新为$mi{n}_{(u,v)\in E_f}h(v)+1$即可。

④初始化
$$\forall (u,v)\in E,f(u,v)=\{\begin{array}{ll}c(u,v)& \text{u=s}\\ 0& \text{u=s}\end{array}$$

$$\forall (u)\in V,h(u)=\{\begin{array}{ll}|V|& \text{u=s}\\ 0& \text{u=s}\end{array}$$
$$e(u)=\sum _{(x,u)\in E}f(x,u)-\sum _{(u,y)\in E}f(u,y)$$
上述将$(s,v)\in E$充满流，并将$h(s)$抬高，使得$(s,v)\notin E$，因为$h(s)>h(v)$，而且$(s,v)$毕竟满流，不必留在残存网络中；上述还将$e(s)$初始化为${\sum }_{(s,v)\in E}f(s,v)$的相反数。

具体进行操作过程中，按照顺序，只要存在结点$u$满足推送或重贴标签操作的条件，就执行对应的操作，直至找不到节点$u$，此时预流推送结束，最终流即为最大流。

3、引入优先队列进行优化

最高标号预流推进算法（High Level Preflow Push）是基于预流推进算法的优先队列实现，该算法优先推送高度高的溢出的结点，算法算法复杂度$O(n^2\sqrt{m})$
HLPP 算法具体过程如下：
①初始化（基于预流推进算法）；
②选择溢出结点（除$s,t$）中高度最高的结点$u$，并对它所有可以推送的边进行推送；
③如果u仍溢出，对它重贴标签，回到步骤②；
④如果没有溢出的结点，算法结束。

4、BFS优化：

HLPP的上界为$O(n^2\sqrt{m})$，但在使用时卡得比较紧；我们可以在初始化高度的时候进行优化。具体来说，我们初始化$h(u)$为$u$ 到$t$的最短距离；特别地$h(s)=n$。

此外，在 BFS 的同时我们顺便检查图的连通性，排除无解的情况。

5、GAP优化

HLPP推送的条件是$h(u)=h(v)+1$ ，而如果在算法的某一时刻，$h(u)=t$的结点个数为0，那么对于$h(u)>t$的结点就永远无法推送超额流到$t$，因此只能送回$s$，那么我们就在这时直接让他们的高度变成$n+1$，以尽快推送回s，减少重贴标签的操作。