diff options
| -rw-r--r-- | graph/graph.tex | 12 | ||||
| -rw-r--r-- | graph/pushRelabel.cpp | 20 | ||||
| -rw-r--r-- | tcr.pdf | bin | 262469 -> 262287 bytes |
3 files changed, 18 insertions, 14 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index ac8e92b..b14ebf4 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -74,18 +74,18 @@ Gut bei sehr dicht besetzten Graphen. \lstinputlisting{graph/pushRelabel.cpp} \subsubsection{Anwendungen} -\begin{itemize} +\begin{itemize}[nosep] \item \textbf{Maximum Edge Disjoint Paths}\newline Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. - \begin{enumerate} + \begin{enumerate}[nosep] \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1. - \item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Kanten. + \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Kanten. \end{enumerate} \item \textbf{Maximum Independent Paths}\newline - Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen. - \begin{enumerate} + Finde die maximale Anzahl an Pfaden von $s$ nach $t$, die keinen Knoten teilen. + \begin{enumerate}[nosep] \item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1. - \item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten. + \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Knoten. \end{enumerate} \item \textbf{Min-Cut}\newline Der maximale Fluss ist gleich dem minimalen Schnitt. diff --git a/graph/pushRelabel.cpp b/graph/pushRelabel.cpp index 13a7bae..7bb1145 100644 --- a/graph/pushRelabel.cpp +++ b/graph/pushRelabel.cpp @@ -5,9 +5,12 @@ struct PushRelabel { PushRelabel(int n) { this->n = n; - memset(capacities, 0L, sizeof(capacities)); memset(flow, 0L, sizeof(flow)); - memset(excess, 0L, sizeof(excess)); memset(height, 0, sizeof(height)); - memset(list, 0, sizeof(list)); memset(seen, 0, sizeof(seen)); + memset(capacities, 0L, sizeof(capacities)); + memset(flow, 0L, sizeof(flow)); + memset(excess, 0L, sizeof(excess)); + memset(height, 0, sizeof(height)); + memset(list, 0, sizeof(list)); + memset(seen, 0, sizeof(seen)); } inline void addEdge(int u, int v, ll c) { capacities[u][v] += c; } @@ -30,8 +33,9 @@ struct PushRelabel { while (excess[u] > 0) { if (seen[u] < n) { int v = seen[u]; - if (capacities[u][v] - flow[u][v] > 0 && height[u] > height[v]) push(u, v); - else seen[u]++; + if (capacities[u][v] - flow[u][v] > 0 && height[u] > height[v]) { + push(u, v); + } else seen[u]++; } else { relabel(u); seen[u] = 0; @@ -39,13 +43,13 @@ struct PushRelabel { void moveToFront(int u) { int temp = list[u]; - for (int i = u; i > 0; i--) - list[i] = list[i - 1]; + for (int i = u; i > 0; i--) list[i] = list[i - 1]; list[0] = temp; } ll maxFlow(int source, int target) { - for (int i = 0, p = 0; i < n; i++) if (i != source && i != target) list[p++] = i; + for (int i = 0, p = 0; i < n; i++) + if (i != source && i != target) list[p++] = i; height[source] = n; excess[source] = LLONG_MAX / 2; Binary files differ |