网络流学习笔记
网络流何为网络流
想要弄清楚网络流，首先要知道网络的概念，通常在运筹学中，网络是指一个有向图$G\ =\ (V,E)$ 。其每条边$(u,v)\in E$都有一个权值$c(u,v)$,称为这条边的流量(Capacity)，还有两个特殊的点，一个是源点(Source),一个是汇点(Sink)在图论中，网络流（英语：Network flow）在作为网络的有向图中分配流，使一条边的流量不会超过它的容量。
网络流的性质
1.容量限制
$\ \ \ \ $ 对于有向图\(G\)中的每一条边上所流经的流量不得超过其容量，即 \(f(u,v) \ ≤ \ c(u,v)\) 。
2.斜对称性
$\ \ \ \ $ 每条边的流量与相反边的流量之和为0，即 \(f(u,v) \ = \ -f(u,v)\)。
3.流守恒性
$\ \ \ \ $ 从源点流出的流量等于汇点流入的流量，即 \(\forall x\in V-\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)\)
$\ \ \ \ $ 现在想象下面一个情景，工厂里有一个运输液体的传输管道，工厂在每条管道的都设置了防止倒流的装置，因为压强问题，所以每条管道在单位时间内的容量有限，这就是一个网络流模型了。
事实上，网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。
网络流的常见问题
$\ \ \ \ $ 网络流问题中常见的有以下三种：最大流，最小割，费用流。
最大流
$\ \ \ \ $ 顾名思义，就是求从源点到汇点的最大流量。下面介绍几种常见的方法，其中Dinic算法几乎能完成所有与最大流相关的问题，因为他的复杂度比较优秀。
Ford-Fulkerson增广
$\ \ \ \ $ Ford-Fulkerson增广是计算最大流算法的一类统称，核心思想是贪心，通过寻找增广路来更新并求解最大流。其中，寻找增广路其实就是寻找从源点到汇点的剩余容量非空的路径，对于一条增广路，我们给每一条\((u,v)\)都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广（Augment）。，但是，在执行过程中，会发现这样的思路有可能导致增广了一些原来不应存在于最大流的路径，怎么办？
$\ \ \ \ $ 我们可以利用网络流的斜对称性，在增广时进行退流操作，如果增广出了\((u,v)\)之间的双向流量实际上可以将经过\((v,u)\)的流量交换来抵消成单向流量。
退流操作带来的「抵消」效果使得我们无需担心我们按照「错误」的顺序选择了增广路。
接下类就是对Ford-Fulkerson增广算法的实现了，对于 Ford–Fulkerson 增广的不同实现，时间复杂度也各不相同。其中较主流的实现有 Edmonds–Karp, Dinic, SAP, ISAP 等算法，我会将自己理解了一些的算法介绍出来，至于其他的，下次一定（doge。
EK算法(Edmonds–Karp)
算法思想
EK算法就是通过BFS不断寻找增广路并不断更新最大流，直至在网络中再也找不到增广路为止。上面讲过，仅仅进行增广操作的话，最后得到的答案是错误的，因此需要退流，而为了追求速度，我们希望能在最短时间找到反向边，我们发现，利用邻接矩阵可以快速的找到反向边，因为邻阶矩阵就具有对称性，但是因为邻接矩阵相当于一个二维数组，无论是空间上还是时间上都不是很好，因此在网络流中的通常使用链式前向星来存储。其中，一个常用的技巧是，我们令边从偶数（通常为 0）开始编号，并在加边时总是紧接着加入其反向边使得它们的编号相邻。由此，我们可以令编号为 \(i\) 的边和编号为 $i \oplus 1 $的边始终保持互为反向边的关系。
存边代码如下：
inline void addedge(int u,int v,int c){
edge[++tot].c = c;
edge.to = v;
edge.from = head;
head = tot;
edge[++tot].c = 0;
edge.to = u;
edge.from = head;
head = tot;
}更新代码如下：
inline void update(){
int x = t;
while (x != s){
int v = pre;
edge.c -= dis; //c是剩余容量
edge.c += dis;
x = edge.to;
}
ans += dis;
}适用范围
时间复杂度为\(O(nm^2)\),一般能处理\(10^3 ~ 10^4\)规模的网络。
完整代码 \(Code\)
#include #define MAXN 505050#define int long longusing namespace std;inline int read(){ int x = 0,f = 1; char c = getchar(); while (!isdigit(c)){ if (c == '-'){ f = -1; } c = getchar(); } while (isdigit(c)){ x = x*10+c-'0'; c = getchar(); } return x*f;}int n,m,s,t;int tot = 1,vis,pre,head,flag;int dis;int ans;struct node { int from,to,c,flow;}edge;inline void addedge(int u,int v,int c){ edge[++tot].to = v; edge.from = head; edge.c = c; head = tot; edge[++tot].to = u; edge.from = head; edge.c = 0; head = tot;}inline bool bfs(){ for (int i=1;i
页:
[1]