diff options
Diffstat (limited to 'content/graph')
| -rw-r--r-- | content/graph/graph.tex | 4 | ||||
| -rw-r--r-- | content/graph/stoerWagner.cpp | 4 |
2 files changed, 4 insertions, 4 deletions
diff --git a/content/graph/graph.tex b/content/graph/graph.tex index b27db0b..040cf3b 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -248,14 +248,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \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{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\min(\abs{V}^2\cdot\abs{E}, F\cdot\abs{E})} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} \sourcecode{graph/dinitzScaling.cpp} \begin{algorithm}{Min-Cost-Max-Flow} \begin{methods} - \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} + \method{mincostflow}{berechnet Fluss}{F\cdot\abs{V}\cdot\abs{E}} \end{methods} \sourcecode{graph/minCostMaxFlow.cpp} \end{algorithm} diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index a122488..c28800e 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -44,10 +44,10 @@ ll stoer_wagner() { state.push_back({cur, c}); } int t = state.back().second; - state.pop_back(); + state.pop_back(); // cut between comp(t) and everything else if (state.empty()) return 0; // graph is not connected?! - merge(state.back().second, t); res = min(res, state.back().first); + merge(state.back().second, t); } return res; } |