diff options
| -rw-r--r-- | graph/graph.tex | 37 | ||||
| -rw-r--r-- | graph/pushRelabel.cpp | 68 | ||||
| -rw-r--r-- | tcr.pdf | bin | 228510 -> 232845 bytes |
3 files changed, 92 insertions, 13 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index 0661ae1..4a617a8 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -77,21 +77,32 @@ Erkennt negative Zyklen. \subsection{Max-Flow} \subsubsection{Capacity Scaling} +Gut bei dünn besetzten Graphen. \lstinputlisting{graph/capacityScaling.cpp} -\subsubsection{Maximum Edge Disjoint Paths} -Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. -\begin{enumerate} - \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. -\end{enumerate} - -\subsubsection{Maximum Independent Paths} -Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen. -\begin{enumerate} - \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. -\end{enumerate} +\subsubsection{Push Relabel} +Gut bei sehr dicht besetzten Graphen. +\lstinputlisting{graph/pushRelabel.cpp} + +\subsubsection{Anwendungen} +\begin{itemize} + \item \textbf{Maximum Edge Disjoint Paths}\newline + Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. + \begin{enumerate} + \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. + \end{enumerate} + \item \textbf{Maximum Independent Paths}\newline + Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen. + \begin{enumerate} + \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. + \end{enumerate} + \item \textbf{Min-Cut}\newline + Der maximale Fluss ist gleich dem minimalen Schnitt. + Bei Quelle $s$ und Senke $t$, partitioniere in $S$ und $T$. + Zu $S$ gehören alle Knoten, die im Residualgraphen von $s$ aus erreichbar sind (Rückwärtskanten beachten). +\end{itemize} \subsection{Min-Cost-Max-Flow} \lstinputlisting{graph/minCostMaxFlow.cpp} diff --git a/graph/pushRelabel.cpp b/graph/pushRelabel.cpp new file mode 100644 index 0000000..13a7bae --- /dev/null +++ b/graph/pushRelabel.cpp @@ -0,0 +1,68 @@ +// Laufzeit: O(|V|^3) +struct PushRelabel { + ll capacities[MAX_V][MAX_V], flow[MAX_V][MAX_V], excess[MAX_V]; + int height[MAX_V], list[MAX_V - 2], seen[MAX_V], n; + + 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)); + } + + inline void addEdge(int u, int v, ll c) { capacities[u][v] += c; } + + void push(int u, int v) { + ll send = min(excess[u], capacities[u][v] - flow[u][v]); + flow[u][v] += send; flow[v][u] -= send; + excess[u] -= send; excess[v] += send; + } + + void relabel(int u) { + int minHeight = INT_MAX / 2; + for (int v = 0; v < n; v++) { + if (capacities[u][v] - flow[u][v] > 0) { + minHeight = min(minHeight, height[v]); + height[u] = minHeight + 1; + }}} + + void discharge(int u) { + 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]++; + } else { + relabel(u); + seen[u] = 0; + }}} + + void moveToFront(int u) { + int temp = list[u]; + 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; + + height[source] = n; + excess[source] = LLONG_MAX / 2; + for (int i = 0; i < n; i++) push(source, i); + + int p = 0; + while (p < n - 2) { + int u = list[p], oldHeight = height[u]; + discharge(u); + if (height[u] > oldHeight) { + moveToFront(p); + p = 0; + } else p++; + } + + ll maxflow = 0L; + for (int i = 0; i < n; i++) maxflow += flow[source][i]; + return maxflow; + } +}; Binary files differ |