From 539d6d81879c7ffa993e626e68889370342ba8e3 Mon Sep 17 00:00:00 2001 From: sshwy Date: Sat, 7 Sep 2019 07:51:35 +0800 Subject: [PATCH] bridge and flow --- docs/graph/bridge.md | 2 - docs/graph/flow/max-flow.md | 270 ++++++++++++++++++++++---------------------- 2 files changed, 135 insertions(+), 137 deletions(-) diff --git a/docs/graph/bridge.md b/docs/graph/bridge.md index d1daf8f6..206edb2c 100644 --- a/docs/graph/bridge.md +++ b/docs/graph/bridge.md @@ -46,8 +46,6 @@ low[u] = min(low[u], num[v]); [洛谷 P3388【模板】割点（割顶）](https://www.luogu.org/problemnew/show/P3388) -### Code - ??? "例题代码" ```cpp /* diff --git a/docs/graph/flow/max-flow.md b/docs/graph/flow/max-flow.md index 62938f0b..c0267257 100644 --- a/docs/graph/flow/max-flow.md +++ b/docs/graph/flow/max-flow.md @@ -332,11 +332,13 @@ struct ISAP { ## Push-Relabel 预流推进算法 -该方法在求解过程中忽略流守恒性，并每次对一个结点更新信息，以求解最大流 +该方法在求解过程中忽略流守恒性，并每次对一个结点更新信息，以求解最大流。 -有 HLPP 的主流算法 +### 通用的预流推进算法 -推送 - 重贴标签算法通过对单个结点的更新操作，直到没有结点需要更新来求解最大流 +首先我们介绍预流推进算法的主要思想，以及一个可行的暴力实现算法。 + +预流推进算法通过对单个结点的更新操作，直到没有结点需要更新来求解最大流。 算法过程维护的流函数不一定保持流守恒性，对于一个结点，我们允许进入结点的流超过流出结点的流，超过的部分被称为结点 $u(u\in V-\{s,t\})$ 的 **超额流** $e(u)$ ： @@ -344,24 +346,24 @@ $$ e(u)=\sum_{(x,u)\in E}f(x,u)-\sum_{(u,y)\in E}f(u,y) $$ -若 $e(u)>0$ ，称结点 $u$ **溢出** . +若 $e(u)>0$ ，称结点 $u$ **溢出** 。 -推送 - 重贴标签算法维护每个结点的高度 $h(u)$ ，并且规定溢出的结点 $u$ 如果要推送超额流，只能向高度小于 $u$ 的结点推送；如果 $u$ 没有相邻的高度小于 $u$ 的结点，就修改 $u$ 的高度（重贴标签）。 +预流推进算法维护每个结点的高度 $h(u)$ ，并且规定溢出的结点 $u$ 如果要推送超额流，只能向高度小于 $u$ 的结点推送；如果 $u$ 没有相邻的高度小于 $u$ 的结点，就修改 $u$ 的高度（重贴标签）。 #### 高度函数 -准确地说，推送 - 重贴标签维护以下的一个映射 $h:V\to \mathbf{N}$ ： +准确地说，预流推进维护以下的一个映射 $h:V\to \mathbf{N}$ ： - $h(s)=|V|,h(t)=0$ - $\forall (u,v)\in E_f,h(u)\leq h(v)+1$ -则称 $h$ 是残存网络 $G_f=(V_f,E_f)$ 的高度函数。 +称 $h$ 是残存网络 $G_f=(V_f,E_f)$ 的高度函数。 引理 1：设 $G_f$ 上的高度函数为 $h$ ，对于任意两个结点 $u,v\in V$ ，如果 $h(u)>h(v)+1$ ，则 $(u,v)$ 不是 $G_f$ 中的边。 算法只会在 $h(u)=h(v)+1$ 的边执行推送。 -#### 推送 -Push +#### 推送（Push） 适用条件：结点 $u$ 溢出，且存在结点 $v((u,v)\in E_f,c(u,v)-f(u,v)>0,h(u)=h(v)+1)$ ，则 push 操作适用于 $(u,v)$ 。 @@ -369,7 +371,7 @@ $$ 如果 $(u,v)$ 在推送完之后满流，将其从残存网络中删除。 -#### 重贴标签 -Relabel +#### 重贴标签（Relabel） 适用条件：如果结点 $u$ 溢出，且 $\forall (u,v)\in E_f,h(u)\leq h(v)$ ，则 relabel 操作适用于 $u$ 。 @@ -394,11 +396,9 @@ $$ 上述将 $(s,v)\in E$ 充满流，并将 $h(s)$ 抬高，使得 $(s,v)\notin E_f$ ，因为 $h(s)>h(v)$ ，而且 $(s,v)$ 毕竟满流，没必要留在残存网络中；上述还将 $e(s)$ 初始化为 $\sum_{(s,v)\in E}f(s,v)$ 的相反数。 -#### 通用执行框架 - -无需按照特定顺序，执行以下过程： +#### 通用算法 -- 只要存在结点 $u$ 满足 push 或 relabel 的条件，就执行对应的操作。 +我们每次扫描整个图，只要存在结点 $u$ 满足 push 或 relabel 操作的条件，就执行对应的操作。 如图，每个结点中间表示编号，左下表示高度值 $h(u)$ ，右下表示超额流 $e(u)$ ，结点颜色的深度也表示结点的高度；边权表示 $c(u,v)-f(u,v)$ ，绿色的边表示满足 $h(u)=h(v)+1$ 的边 $(u,v)$ （即残存网络的边 $E_f$ ）： @@ -414,42 +414,42 @@ $$ 可以发现，最后的超额流一部分回到了 $s$ ，且除了源点汇点，其他结点都没有溢出；这时的流函数 $f$ 满足流守恒性，为最大流，即 $e(t)$ 。 -#### 核心代码 - -```cpp -const int N = 1e4 + 4, M = 1e5 + 5, INF = 0x3f3f3f3f; -int n, m, s, t, maxflow, tot; -int ht[N], ex[N]; -void init() { // 初始化 - for (int i = h[s]; i; i = e[i].nex) { - const int &v = e[i].t; - ex[v] = e[i].v, ex[s] -= ex[v], e[i ^ 1].v = e[i].v, e[i].v = 0; - } - ht[s] = n; -} -bool push(int ed) { - const int &u = e[ed ^ 1].t, &v = e[ed].t; - int flow = min(ex[u], e[ed].v); - ex[u] -= flow, ex[v] += flow, e[ed].v -= flow, e[ed ^ 1].v += flow; - return ex[u]; // 如果 u 仍溢出，返回 1 -} -void relabel(int u) { - ht[u] = INF; - for (int i = h[u]; i; i = e[i].nex) - if (e[i].v) ht[u] = min(ht[u], ht[e[i].t]); - ++ht[u]; -} -``` +???+ "核心代码" + + ```cpp + const int N = 1e4 + 4, M = 1e5 + 5, INF = 0x3f3f3f3f; + int n, m, s, t, maxflow, tot; + int ht[N], ex[N]; + void init() { // 初始化 + for (int i = h[s]; i; i = e[i].nex) { + const int &v = e[i].t; + ex[v] = e[i].v, ex[s] -= ex[v], e[i ^ 1].v = e[i].v, e[i].v = 0; + } + ht[s] = n; + } + bool push(int ed) { + const int &u = e[ed ^ 1].t, &v = e[ed].t; + int flow = min(ex[u], e[ed].v); + ex[u] -= flow, ex[v] += flow, e[ed].v -= flow, e[ed ^ 1].v += flow; + return ex[u]; // 如果 u 仍溢出，返回 1 + } + void relabel(int u) { + ht[u] = INF; + for (int i = h[u]; i; i = e[i].nex) + if (e[i].v) ht[u] = min(ht[u], ht[e[i].t]); + ++ht[u]; + } + ``` ### HLPP 算法 -最高标号预流推进算法（High Level Preflow Push）是基于推送 - 重贴标签算法的优先队列实现，该算法优先推送高度高的溢出的结点，算法算法复杂度 $O(n^2\sqrt m)$ 。 +最高标号预流推进算法（High Level Preflow Push）是基于预流推进算法的优先队列实现，该算法优先推送高度高的溢出的结点，算法算法复杂度 $O(n^2\sqrt m)$ 。 -具体地说，HLPP 维护以下过程： +具体地说，HLPP 算法过程如下： -1. 初始化（基于推送 - 重贴标签算法）； +1. 初始化（基于预流推进算法）； 2. 选择溢出结点（除 $s,t$ ）中高度最高的结点 $u$ ，并对它所有可以推送的边进行推送； -3. 如果 $u$ 仍溢出，对它重贴标签，回到 2； +3. 如果 $u$ 仍溢出，对它重贴标签，回到步骤 2； 4. 如果没有溢出的结点，算法结束。 #### BFS 优化 @@ -464,101 +464,101 @@ HLPP 的上界为 $O(n^2\sqrt m)$ ，但在使用时卡得比较紧；我们可 HLPP 推送的条件是 $h(u)=h(v)+1$ ，而如果在算法的某一时刻， $h(u)=t$ 的结点个数为 $0$ ，那么对于 $h(u)>t$ 的结点就永远无法推送超额流到 $t$ ，因此只能送回 $s$ ，那么我们就在这时直接让他们的高度变成 $n+1$ ，以尽快推送回 $s$ ，减少重贴标签的操作。 -#### LuoguP4722【模板】最大流 加强版/预流推进 - -```cpp -#include -#include -#include -using namespace std; -const int N = 1e4 + 4, M = 2e5 + 5, INF = 0x3f3f3f3f; -int n, m, s, t; - -struct qxx { - int nex, t, v; -}; -qxx e[M * 2]; -int h[N], cnt = 1; -void add_path(int f, int t, int v) { e[++cnt] = (qxx){h[f], t, v}, h[f] = cnt; } -void add_flow(int f, int t, int v) { - add_path(f, t, v); - add_path(t, f, 0); -} +???+ "LuoguP4722【模板】最大流 加强版/预流推进" + + ```cpp + #include + #include + #include + using namespace std; + const int N = 1e4 + 4, M = 2e5 + 5, INF = 0x3f3f3f3f; + int n, m, s, t; + + struct qxx { + int nex, t, v; + }; + qxx e[M * 2]; + int h[N], cnt = 1; + void add_path(int f, int t, int v) { e[++cnt] = (qxx){h[f], t, v}, h[f] = cnt; } + void add_flow(int f, int t, int v) { + add_path(f, t, v); + add_path(t, f, 0); + } -int ht[N], ex[N], gap[N]; // 高度；超额流；gap 优化 -bool bfs_init() { - memset(ht, 0x3f, sizeof(ht)); - queue q; - q.push(t), ht[t] = 0; - while (q.size()) { // 反向 BFS, 遇到没有访问过的结点就入队 - int u = q.front(); - q.pop(); - for (int i = h[u]; i; i = e[i].nex) { - const int &v = e[i].t; - if (e[i ^ 1].v && ht[v] > ht[u] + 1) ht[v] = ht[u] + 1, q.push(v); + int ht[N], ex[N], gap[N]; // 高度；超额流；gap 优化 + bool bfs_init() { + memset(ht, 0x3f, sizeof(ht)); + queue q; + q.push(t), ht[t] = 0; + while (q.size()) { // 反向 BFS, 遇到没有访问过的结点就入队 + int u = q.front(); + q.pop(); + for (int i = h[u]; i; i = e[i].nex) { + const int &v = e[i].t; + if (e[i ^ 1].v && ht[v] > ht[u] + 1) ht[v] = ht[u] + 1, q.push(v); + } + } + return ht[s] != INF; // 如果图不连通，返回 0 } - } - return ht[s] != INF; // 如果图不连通，返回 0 -} -struct cmp { - bool operator()(int a, int b) const { return ht[a] < ht[b]; } -}; // 伪装排序函数 -priority_queue, cmp> pq; // 将需要推送的结点以高度高的优先 -bool vis[N]; // 是否在优先队列中 -int push(int u) { // 尽可能通过能够推送的边推送超额流 - for (int i = h[u]; i; i = e[i].nex) { - const int &v = e[i].t, &w = e[i].v; - if (!w || ht[u] != ht[v] + 1) continue; - int k = min(w, ex[u]); // 取到剩余容量和超额流的最小值 - ex[u] -= k, ex[v] += k, e[i].v -= k, e[i ^ 1].v += k; // push - if (v != s && v != t && !vis[v]) - pq.push(v), vis[v] = 1; // 推送之后，v 必然溢出，则入堆，等待被推送 - if (!ex[u]) return 0; // 如果已经推送完就返回 - } - return 1; -} -void relabel(int u) { // 重贴标签（高度） - ht[u] = INF; - for (int i = h[u]; i; i = e[i].nex) - if (e[i].v) ht[u] = min(ht[u], ht[e[i].t]); - ++ht[u]; -} -int hlpp() { // 返回最大流 - if (!bfs_init()) return 0; // 图不连通 - ht[s] = n; - memset(gap, 0, sizeof(gap)); - for (int i = 1; i <= n; i++) - if (ht[i] != INF) gap[ht[i]]++; // 初始化 gap - for (int i = h[s]; i; i = e[i].nex) { - const int v = e[i].t, w = e[i].v; // 队列初始化 - if (!w) continue; - ex[s] -= w, ex[v] += w, e[i].v -= w, e[i ^ 1].v += w; // 注意取消 w 的引用 - if (v != s && v != t && !vis[v]) pq.push(v), vis[v] = 1; // 入队 - } - while (pq.size()) { - int u = pq.top(); - pq.pop(), vis[u] = 0; - while (push(u)) { // 仍然溢出 - // 如果 u 结点原来所在的高度没有结点了，相当于出现断层 - if (!--gap[ht[u]]) - for (int i = 1; i <= n; i++) - if (i != s && i != t && ht[i] > ht[u] && ht[i] < n + 1) ht[i] = n + 1; - relabel(u); - ++gap[ht[u]]; // 新的高度，更新 gap + struct cmp { + bool operator()(int a, int b) const { return ht[a] < ht[b]; } + }; // 伪装排序函数 + priority_queue, cmp> pq; // 将需要推送的结点以高度高的优先 + bool vis[N]; // 是否在优先队列中 + int push(int u) { // 尽可能通过能够推送的边推送超额流 + for (int i = h[u]; i; i = e[i].nex) { + const int &v = e[i].t, &w = e[i].v; + if (!w || ht[u] != ht[v] + 1) continue; + int k = min(w, ex[u]); // 取到剩余容量和超额流的最小值 + ex[u] -= k, ex[v] += k, e[i].v -= k, e[i ^ 1].v += k; // push + if (v != s && v != t && !vis[v]) + pq.push(v), vis[v] = 1; // 推送之后，v 必然溢出，则入堆，等待被推送 + if (!ex[u]) return 0; // 如果已经推送完就返回 + } + return 1; } - } - return ex[t]; -} -int main() { - scanf("%d%d%d%d", &n, &m, &s, &t); - for (int i = 1, u, v, w; i <= m; i++) { - scanf("%d%d%d", &u, &v, &w); - add_flow(u, v, w); - } - printf("%d", hlpp()); - return 0; -} -``` + void relabel(int u) { // 重贴标签（高度） + ht[u] = INF; + for (int i = h[u]; i; i = e[i].nex) + if (e[i].v) ht[u] = min(ht[u], ht[e[i].t]); + ++ht[u]; + } + int hlpp() { // 返回最大流 + if (!bfs_init()) return 0; // 图不连通 + ht[s] = n; + memset(gap, 0, sizeof(gap)); + for (int i = 1; i <= n; i++) + if (ht[i] != INF) gap[ht[i]]++; // 初始化 gap + for (int i = h[s]; i; i = e[i].nex) { + const int v = e[i].t, w = e[i].v; // 队列初始化 + if (!w) continue; + ex[s] -= w, ex[v] += w, e[i].v -= w, e[i ^ 1].v += w; // 注意取消 w 的引用 + if (v != s && v != t && !vis[v]) pq.push(v), vis[v] = 1; // 入队 + } + while (pq.size()) { + int u = pq.top(); + pq.pop(), vis[u] = 0; + while (push(u)) { // 仍然溢出 + // 如果 u 结点原来所在的高度没有结点了，相当于出现断层 + if (!--gap[ht[u]]) + for (int i = 1; i <= n; i++) + if (i != s && i != t && ht[i] > ht[u] && ht[i] < n + 1) ht[i] = n + 1; + relabel(u); + ++gap[ht[u]]; // 新的高度，更新 gap + } + } + return ex[t]; + } + int main() { + scanf("%d%d%d%d", &n, &m, &s, &t); + for (int i = 1, u, v, w; i <= m; i++) { + scanf("%d%d%d", &u, &v, &w); + add_flow(u, v, w); + } + printf("%d", hlpp()); + return 0; + } + ``` 感受一下运行过程 -- 2.11.0