diff options
Diffstat (limited to 'maxFlow')
| -rw-r--r-- | maxFlow/edmondsKarp.cpp | 34 | ||||
| -rw-r--r-- | maxFlow/maxFlow.tex | 4 | ||||
| -rw-r--r-- | maxFlow/q.log | 25 |
3 files changed, 63 insertions, 0 deletions
diff --git a/maxFlow/edmondsKarp.cpp b/maxFlow/edmondsKarp.cpp new file mode 100644 index 0000000..c82b141 --- /dev/null +++ b/maxFlow/edmondsKarp.cpp @@ -0,0 +1,34 @@ +int s, t, f; //source, target, single flow +int res[100][100]; //adj-matrix +vector< vector<int> > adjList; +int p[100]; //bfs spanning tree + +void augment(int v, int minEdge) { + if (v == s) { f = minEdge; return; } + else if (p[v] != -1) { + augment(p[v], min(minEdge, res[p[v]][v])); + res[p[v]][v] -= f; res[v][p[v]] += f; +}} + +int main() { + //inititalize res, adjList, s, t + int mf = 0; + while (true) { + f = 0; + bitset<100> vis; vis[s] = true; + queue<int> q; q.push(s); + memset(p, -1, sizeof(p)); + while (!q.empty()) { //BFS + int u = q.front(); q.pop(); + if (u == t) break; + for (int j = 0; j < (int)adjList[u].size(); j++) { + int v = adjList[u][j]; + if (res[u][v] > 0 && !vis[v]) { + vis[v] = true; q.push(v); p[v] = u; + }}} + + augment(t, INF); //add found path to max flow + if (f == 0) break; + mf += f; +}} +//max flow in mf}
\ No newline at end of file diff --git a/maxFlow/maxFlow.tex b/maxFlow/maxFlow.tex new file mode 100644 index 0000000..a88e5ff --- /dev/null +++ b/maxFlow/maxFlow.tex @@ -0,0 +1,4 @@ +\section{Max Flows} +\subsection{\textsc{Edmonds-Karp}-Algorithmus} + +\lstinputlisting{maxFlow/edmondsKarp.cpp}
\ No newline at end of file diff --git a/maxFlow/q.log b/maxFlow/q.log new file mode 100644 index 0000000..2a742c3 --- /dev/null +++ b/maxFlow/q.log @@ -0,0 +1,25 @@ +This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2014.5.4) 25 OCT 2014 13:42 +entering extended mode + restricted \write18 enabled. + %&-line parsing enabled. +**tcr.tex +(/usr/share/texlive/texmf-dist/tex/latex/tools/q.tex +LaTeX2e <2011/06/27> +Babel <3.9h> and hyphenation patterns for 7 languages loaded. +File ignored +) +! Emergency stop. +<*> tcr.tex + +*** (job aborted, no legal \end found) + + +Here is how much of TeX's memory you used: + 7 strings out of 494976 + 248 string characters out of 6179138 + 46219 words of memory out of 5000000 + 3331 multiletter control sequences out of 15000+600000 + 3640 words of font info for 14 fonts, out of 8000000 for 9000 + 14 hyphenation exceptions out of 8191 + 5i,0n,1p,87b,8s stack positions out of 5000i,500n,10000p,200000b,80000s +! ==> Fatal error occurred, no output PDF file produced! |