diff options
| -rw-r--r-- | content/graph/dinitzScaling.cpp (renamed from content/graph/dinicScaling.cpp) | 0 | ||||
| -rw-r--r-- | content/graph/graph.tex | 4 | ||||
| -rw-r--r-- | content/other/other.tex | 2 | ||||
| -rw-r--r-- | test/graph/dinitzScaling.cpp (renamed from test/graph/dinicScaling.cpp) | 14 | ||||
| -rw-r--r-- | test/graph/pushRelabel.cpp | 12 |
5 files changed, 16 insertions, 16 deletions
diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinitzScaling.cpp index fd82296..fd82296 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinitzScaling.cpp diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 6e8e20b..0692d20 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -215,12 +215,12 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/pushRelabel.cpp} } -\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} +\subsubsection{\textsc{Dinitz}'s Algorithm mit Capacity Scaling} \begin{methods} \method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} -\sourcecode{graph/dinicScaling.cpp} +\sourcecode{graph/dinitzScaling.cpp} \begin{algorithm}{Min-Cost-Max-Flow} \begin{methods} diff --git a/content/other/other.tex b/content/other/other.tex index 8896962..dce0f3d 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -123,7 +123,7 @@ c'(s',v)&=\sum_{u\in{}V}d(u,v)&c'(v,t')&=\sum_{u\in{}V}d(v,u)\\[-0.5ex]
c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x
\end{align*}
- Löse Fluss auf $G'$ mit \textsc{Dinic's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
+ Löse Fluss auf $G'$ mit \textsc{Dinitz's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
\item \textbf{\textsc{Johnson}s Reweighting Algorithm:}
Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen.
Falls es einen negativen Zyklus gibt abrrechen.
diff --git a/test/graph/dinicScaling.cpp b/test/graph/dinitzScaling.cpp index 967d6b1..c06d486 100644 --- a/test/graph/dinicScaling.cpp +++ b/test/graph/dinitzScaling.cpp @@ -1,6 +1,6 @@ #include "../util.h" -namespace dinic { -#include <graph/dinicScaling.cpp> +namespace dinitz { +#include <graph/dinitzScaling.cpp> } namespace pushRelabel { @@ -13,20 +13,20 @@ void stress_test() { int n = Random::integer<int>(2, 30); int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); - dinic::adj.assign(n, {}); + dinitz::adj.assign(n, {}); pushRelabel::adj.assign(n, {}); Graph<NoData, true> g(n); g.erdosRenyi(m); g.forEdges([](int a, int b){ ll w = Random::integer<ll>(1, 1'000'000'000'000ll); - dinic::addEdge(a, b, w); + dinitz::addEdge(a, b, w); pushRelabel::addEdge(a, b, w); }); - ll got = dinic::maxFlow(0, n - 1); + ll got = dinitz::maxFlow(0, n - 1); ll expected = pushRelabel::maxFlow(0, n - 1); - + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } @@ -36,7 +36,7 @@ void stress_test() { constexpr int N = 50000; constexpr int M = 200000; void performance_test() { - using namespace dinic; + using namespace dinitz; timer t; Graph<NoData> g(N); g.erdosRenyi(M); diff --git a/test/graph/pushRelabel.cpp b/test/graph/pushRelabel.cpp index ac3b079..42c2e57 100644 --- a/test/graph/pushRelabel.cpp +++ b/test/graph/pushRelabel.cpp @@ -1,6 +1,6 @@ #include "../util.h" -namespace dinic { -#include <graph/dinicScaling.cpp> +namespace dinitz { +#include <graph/dinitzScaling.cpp> } namespace pushRelabel { @@ -13,20 +13,20 @@ void stress_test() { int n = Random::integer<int>(2, 30); int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); - dinic::adj.assign(n, {}); + dinitz::adj.assign(n, {}); pushRelabel::adj.assign(n, {}); Graph<NoData, true> g(n); g.erdosRenyi(m); g.forEdges([](int a, int b){ ll w = Random::integer<ll>(1, 1'000'000'000'000ll); - dinic::addEdge(a, b, w); + dinitz::addEdge(a, b, w); pushRelabel::addEdge(a, b, w); }); ll got = pushRelabel::maxFlow(0, n - 1); - ll expected = dinic::maxFlow(0, n - 1); - + ll expected = dinitz::maxFlow(0, n - 1); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries += n; } |