From 662e0658ccd4b402da6313dcccb9f8cb2611d198 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Tue, 15 Jan 2019 18:50:35 +0800 Subject: [PATCH] style: format markdown files with remark-lint --- docs/graph/flow.md | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) diff --git a/docs/graph/flow.md b/docs/graph/flow.md index 18ad6799..de3386b9 100644 --- a/docs/graph/flow.md +++ b/docs/graph/flow.md @@ -45,29 +45,29 @@ 讲一下一些小细节。如果你是用邻接矩阵的话，反向边直接就是从 $table[x,y]$ 变成 $table[y,x]$。如果是常用的链式前向星，那么在加入边的时候就要先加入反向边。那么在用的时候呢，我们直接 $i\operatorname{xor}1$ 就可以了 ($i$ 为边的编号)。为什么呢? 相信大家都是知道 $\operatorname{xor}$ 的，那么我们在加入正向边后加入反向边，就是靠近的，所以可以使用 $\operatorname{xor}$。我们还要注意一开始的编号要设置为 $tot=1$，因为边要从编号 $2$ 开始，这样子 $\operatorname{xor}$ 对编号 $2,3$ 的边才有效果。 -EK算法的时间复杂度上限为$O(n^2m)$（其中$n$为点数，$m$为边数）。效率还有很大提升空间。 +EK 算法的时间复杂度上限为$O(n^2m)$（其中$n$为点数，$m$为边数）。效率还有很大提升空间。 ### Dinic -**Dinic算法**的过程是这样的：每次增广前，我们先用bfs来将图分层。设源点的层数为0，那么一个点的层数便是它离源点的最近距离。 +**Dinic 算法**的过程是这样的：每次增广前，我们先用 bfs 来将图分层。设源点的层数为 0，那么一个点的层数便是它离源点的最近距离。 通过分层，我们可以干两件事情： -1. 如果不存在到汇点的增广路（即汇点的层数不存在），我们即可停止增广。 -2. 确保我们找到的增广路是最短的。（原因见下文） +1. 如果不存在到汇点的增广路（即汇点的层数不存在），我们即可停止增广。 +2. 确保我们找到的增广路是最短的。（原因见下文） -接下来是DFS找增广路的过程。 +接下来是 DFS 找增广路的过程。 -我们每次找增广路的时候，都只找比当前点层数多1的点进行增广（这样就可以确保我们找到的增广路是最短的）。 +我们每次找增广路的时候，都只找比当前点层数多 1 的点进行增广（这样就可以确保我们找到的增广路是最短的）。 -Dinic算法有两个优化： +Dinic 算法有两个优化： -1. **多路增广**：每次找到一条增广路的时候，如果残余流量没有用完怎么办呢？我们可以利用残余部分流量，再找出一条增广路。这样就可以在一次DFS中找出多条增广路，大大提高了算法的效率。 -2. **当前弧优化**：如果一条边已经被增广过，那么它就没有可能被增广第二次。那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边。 +1. **多路增广**：每次找到一条增广路的时候，如果残余流量没有用完怎么办呢？我们可以利用残余部分流量，再找出一条增广路。这样就可以在一次 DFS 中找出多条增广路，大大提高了算法的效率。 +2. **当前弧优化**：如果一条边已经被增广过，那么它就没有可能被增广第二次。那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边。 -设点数为$n$，边数为$m$，那么Dinic算法的时间复杂度上限是$O(nm^2)$，在稀疏图上效率和EK算法相当，但在稠密图上效率要比EK算法高很多。 +设点数为$n$，边数为$m$，那么 Dinic 算法的时间复杂度上限是$O(nm^2)$，在稀疏图上效率和 EK 算法相当，但在稠密图上效率要比 EK 算法高很多。 -特别地，在求解二分图最大匹配问题时，可以证明Dinic算法的时间复杂度是$O(n \sqrt{m})$。 +特别地，在求解二分图最大匹配问题时，可以证明 Dinic 算法的时间复杂度是$O(n \sqrt{m})$。 ### ISAP -- 2.11.0