diff options
| -rw-r--r-- | graph/graph.tex | 3 | ||||
| -rw-r--r-- | graph/minCostMaxFlow.cpp | 34 | ||||
| -rw-r--r-- | tcr.pdf | bin | 212442 -> 214829 bytes | |||
| -rw-r--r-- | toDo.txt | 3 |
4 files changed, 38 insertions, 2 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index d4bf9d5..04bb93e 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -67,6 +67,9 @@ Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen. \item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten. \end{enumerate} +\subsection{Min-Cost-Max-Flow} +\lstinputlisting{graph/minCostMaxFlow.cpp} + \subsection{Maximal Cardinatlity Bipartite Matching}\label{kuhn} \lstinputlisting{graph/maxCarBiMatch.cpp} diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp new file mode 100644 index 0000000..56e6223 --- /dev/null +++ b/graph/minCostMaxFlow.cpp @@ -0,0 +1,34 @@ +int s, t, f, c; //source, target, single flow, single cost +int res[MAX_V][MAX_V]; //residual graph +vector<edge> edges; //edge list +vector<int> p, dist; //parent pointer, dist field + +void augment(int v, int minEdge) { + if (v == s) { f = minEdge; c = minEdge * dist[t]; return; } //c = minEdge * dist[t] added + else if (p[v] != -1) { + augment(p[v], min(minEdge, res[p[v]][v])); + res[p[v]][v] -= f; res[v][p[v]] += f; +}} + +//first inititalize res, edges, s and t +int minCostMaxFlow(int v) { //v is number of vertices + int mf = 0, mc = 0, i, j; + while (true) { + f = 0; c = 0; + dist.assign(v, INF); dist[s] = 0; + p.assign(v, -1); + for (i = 0; i < v - 1; i++) { //Bellmann-Ford + for (j = 0; j < (int)edges.size(); j++) { + if (res[edges[j].from][edges[j].to] > 0 && dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + dist[edges[j].to] = dist[edges[j].from] + edges[j].cost; + p[edges[j].to] = edges[j].from; + } + } + } + + augment(t, INF); //add found path to max flow, method as in EdmondsKarp + if (f == 0) break; + mf += f; mc += c; + } + return mf; //returns max flow, for in cost, use mc +}
\ No newline at end of file Binary files differ@@ -1,2 +1 @@ -- kondensierter Graph -- min cost max flow
\ No newline at end of file +- kondensierter Graph
\ No newline at end of file |