From 424c6746c62d56710616f4b3b9519efaf5824413 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Fri, 6 Sep 2019 20:10:13 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/graph/flow/max-flow.md | 3 +-- docs/graph/flow/min-cost.md | 6 +++--- 2 files changed, 4 insertions(+), 5 deletions(-) diff --git a/docs/graph/flow/max-flow.md b/docs/graph/flow/max-flow.md index 02a34521..7e0fa3f2 100644 --- a/docs/graph/flow/max-flow.md +++ b/docs/graph/flow/max-flow.md @@ -415,7 +415,6 @@ $$ 可以发现,最后的超额流一部分回到了 $s$ ,且除了源点汇点,其他结点都没有溢出;这时的流函数 $f$ 满足流守恒性,为最大流,即 $e(t)$ 。 ???+ "核心代码" - ```cpp const int N = 1e4 + 4, M = 1e5 + 5, INF = 0x3f3f3f3f; int n, m, s, t, maxflow, tot; @@ -463,7 +462,6 @@ 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 @@ -471,6 +469,7 @@ HLPP 推送的条件是 $h(u)=h(v)+1$ ,而如果在算法的某一时刻, $h using namespace std; const int N = 1e4 + 4, M = 2e5 + 5, INF = 0x3f3f3f3f; int n, m, s, t; + ``` struct qxx { int nex, t, v; diff --git a/docs/graph/flow/min-cost.md b/docs/graph/flow/min-cost.md index 8c2ad95c..9b50b2ec 100644 --- a/docs/graph/flow/min-cost.md +++ b/docs/graph/flow/min-cost.md @@ -25,7 +25,6 @@ 相当于把 $w(u,v)$ 作为边权,在残存网络上求最短路 ???+ "核心代码" - ```cpp struct qxx { int nex, t, v, c; @@ -39,6 +38,7 @@ add_path(f, t, v, c); add_path(t, f, 0, -c); } + ``` int dis[N], pre[N], incf[N]; bool vis[N]; @@ -72,11 +72,11 @@ ## 类 Dinic 算法 -我们可以在 Dinic 算法的基础上进行改进,把 BFS 求分层图改为用 SPFA (由于有负权边,所以不能直接用 Dijkstra )来求一条单位费用之和最小的路径,也就是把 $w(u,v)$ 当做边权然后在残量网络上求最短路,当然在 DFS 中也要略作修改。这样就可以求得网络流图的 **最小费用最大流** 了。 +我们可以在 Dinic 算法的基础上进行改进,把 BFS 求分层图改为用 SPFA(由于有负权边,所以不能直接用 Dijkstra)来求一条单位费用之和最小的路径,也就是把 $w(u,v)$ 当做边权然后在残量网络上求最短路,当然在 DFS 中也要略作修改。这样就可以求得网络流图的 **最小费用最大流** 了。 如何建 **反向边** ?对于一条边 $(u,v,w,c)$ (其中 $w$ 和 $c$ 分别为容量和费用),我们建立正向边 $(u,v,w,c)$ 和反向边 $(v,u,0,-c)$ (其中 $-c$ 是使得从反向边经过时退回原来的费用)。 - **优化** :如果你是“关于 SPFA ,它死了”言论的追随者,那么你可以使用 Primal-Dual 原始对偶算法将 SPFA 改成 Dijkstra ! + **优化** :如果你是“关于 SPFA,它死了”言论的追随者,那么你可以使用 Primal-Dual 原始对偶算法将 SPFA 改成 Dijkstra! **时间复杂度** :可以证明上界为 $O(nmf)$ ,其中 $f$ 表示流量。 -- 2.11.0