Dinic算法（研究总结，⽹络流）
Dinic算法（研究总结，⽹络流）
⽹络流是信息学竞赛中的常见类型，笔者刚学习了最⼤流Dinic算法，简单记录⼀下⽹络流基本概念
什么是⽹络流
在⼀个有向图上选择⼀个源点，⼀个汇点，每⼀条边上都有⼀个流量上限（以下称为容量），即经过这条边的流量不能超过这个上界，同
时，除源点和汇点外，所有点的⼊流和出流都相等，⽽源点只有流出的流，汇点只有汇⼊的流。这样的图叫做⽹络流。
所谓⽹络或容量⽹络指的是⼀个连通的赋权有向图 D= （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上
的容量。此外顶点集中包括⼀个起点和⼀个终点。⽹络上的流就是由起点流向终点的可⾏流，这是定义在⽹络上的⾮负函数，它⼀⽅⾯受到容量的限制，另⼀⽅⾯除去起点和终点以外，在所有中途点要求保持流⼊量和流出量是平衡的。（引⾃百度百科）
定义
我们定义：
源点：只有流出去的点
汇点：只有流进来的点
流量：⼀条边上流过的流量
容量：⼀条边上可供流过的最⼤流量
残量：⼀条边上的容量-流量
⼏个基本性质
基本性质⼀：
对于任何⼀条流，总有流量<=容量
这是很显然的
基本性质⼆
对于任何⼀个不是源点或汇点的点u，总有
这个也很显然，即⼀个点（除源点和汇点）的⼊流和出流相等
基本性质三
对于任何⼀条有向边(u,v)，总有
这个看起来并不是很好理解，它的意思就是⼀条边的反边上的流是这条边的流的相反数，可以这么想，就是如果有k[u][v]的流从u流向v，也
就相当于有-k[v][u]的流从v流向u。这条性质⾮常重要。
⽹络流最⼤流⽹络流的最⼤流算法就是指的⼀个流量的⽅案使得⽹络中流量最⼤。
⽹络流最⼤流的求解
⽹络流的所有算法都是基于⼀种增⼴路的思想，下⾯⾸先简要的说⼀下增⼴路思想，其基本步骤如下：（其中表⽰到的流量）1.找到⼀条从源点到汇点的路径，使得路径上任意⼀条边的残量>0（注意是⼩于⽽不是⼩于等于，这意味着这条边还可以分配流
量），这条路径便称为增⼴路2.找到这条路径上最⼩的F[u][v]（我们设F[u][v]表⽰u->v这条边上的残量即剩余流量），下⾯记为flow
网络流算法及其应用
5.1 基本概念
在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。
1．问题描述
如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。
图5-1 图5-2
2．网络与网络流
给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。
所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。
3．可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：
网络流构图总结
网络流专题研究
福州一中肖汉骏
预备知识(参见Amber论文)
网络和流
残留网络和增广路径
最大流和最小割
主要算法
最大流
增广路方法Ford-Fulkerson method
一般增广路算法Labeling algorithm
连续增广路算法
由陈启峰提出，竞赛中相当实用，近于O(m)
容量缩放增广路算法Capacity scaling algorithm
最短增广路算法Edmonds-Karp algorithm
连续最短增广路算法Successive shortest augmenting path
algorithm (Dinic augorithm)
预流推进方法Preflow-push method
一般预流推进算法Generic preflow-push algorithm
先进先出预流推进算法FIFO preflow-push algorithm
最高标号预流推进算法Highest-label preflow-push algorithm
(Relabel-to-Front algorithm)
最小费用流
最小费用路方法
一般最小费用路算法(SPFA找增广路，复杂度近于O(mf)，竞赛中实用)
注意：初始流的费用必须保证是在所有同流量流中最小的。
原始-对偶算法
消圈方法 一般消圈算法
网络单纯形法
常见变形
多源多汇问题
可通过增添超级源和超级汇解决。
点有容量或费用
可以尝试拆一个点为一入点一出点，将点的限制转移到入点到出点的边上。
重边、无向边和自环的处理
对于使用边链表存储的图，重边一般不需要特殊处理。但当重边的数量太多以至于显著影响算法效率时，可以考虑将相同起点终点的边的容量相加。
而无向边则可以看做是在两个方向上都只要求Flow小于Capa即可。
而最小费用流问题中的重边却反而成为一种处理复杂权函数的手段。根据题目要求或者问题性质，可以为重边列出一个费用随流量变化的函数。如果将这个函数的离散点顺次相连，得到的是若干斜率不断增大的折线段，则可为每段折线段建立一条边，根据最小费用流的性质，重边选择的必然是连续的一段。
网络流 习题 答案
网络流是图论中一个重要的概念，它在计算机科学和运筹学等领域有着广泛的应用。网络流问题可以抽象为在一个有向图中找到从源点到汇点的最大流量或最小割问题。解决网络流问题的算法有很多种，其中最著名的是Ford-Fulkerson算法和Edmonds-Karp算法。
在解决网络流问题时，我们首先需要定义图的结构。一个网络流图由一组节点和一组有向边组成。每条边都有一个容量，表示该边上最大可以通过的流量。图中有一个特殊的源点和一个汇点，源点是流量的起点，汇点是流量的终点。我们的目标是找到从源点到汇点的最大流量。
Ford-Fulkerson算法是一种经典的解决网络流问题的方法。它的基本思想是不断寻找增广路径，即从源点到汇点的一条路径，沿途每条边上的流量都小于等于该边的容量。通过增加这条路径上的流量，我们可以逐步增大整个网络的流量。当无法找到增广路径时，算法终止，此时的流量即为最大流量。
Edmonds-Karp算法是Ford-Fulkerson算法的一个改进版本。它通过使用广度优先搜索来寻找增广路径，从而保证每次找到的路径都是最短的。这样可以大大提高算法的效率，尤其是在图中边的容量差异较大时。Edmonds-Karp算法的时间复杂度为O(V*E^2)，其中V是节点数，E是边数。
除了上述两种算法外，还有其他一些解决网络流问题的方法，如Dinic算法和Push-Relabel算法等。这些算法在不同的应用场景下有各自的优势，选择适合的算法可以提高问题的求解效率。
网络流问题的应用非常广泛。在运输领域，网络流可以用来优化货物的运输方案，使得总运输成本最小。在通信网络中，网络流可以用来优化数据的传输路径，提高网络的吞吐量。在社交网络中，网络流可以用来分析信息的传播过程，预测病毒传播的路径等。
总之，网络流是图论中一个重要的概念，它在计算机科学和运筹学等领域有广泛的应用。解决网络流问题的算法有很多种，每种算法都有其适用的场景。通过合理选择算法，我们可以高效地解决各种网络流问题，为实际应用提供有力的支持。
