min cost max flow

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
diff --git a/tcr.pdf b/tcr.pdf
index 045dc9e..4777e9a 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/toDo.txt b/toDo.txt
index f58eaba..57d1543 100644
--- a/toDo.txt
+++ b/toDo.txt
@@ -1,2 +1 @@
-- kondensierter Graph
-- min cost max flow
\ No newline at end of file
+- kondensierter Graph
\ No newline at end of file