diff options
| -rw-r--r-- | graph/graph.tex | 3 | ||||
| -rw-r--r-- | graph/maxCarBiMatch.cpp | 24 | ||||
| -rw-r--r-- | tcr.pdf | bin | 172283 -> 174553 bytes |
3 files changed, 27 insertions, 0 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index 79404d4..8d525f6 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -66,3 +66,6 @@ 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} +\subsubsection{Maximal Cardinatlity Bipartite Mathcing} +\lstinputlisting{graph/maxCarBiMatch.cpp} + diff --git a/graph/maxCarBiMatch.cpp b/graph/maxCarBiMatch.cpp new file mode 100644 index 0000000..d46ce9d --- /dev/null +++ b/graph/maxCarBiMatch.cpp @@ -0,0 +1,24 @@ +vector< vector<int> > adjlist; +vector<int> pairs; //for every node, stores the matching node on the other side or -1 +vector<bool> visited; + +bool dfs(int i) { + if (visited[i]) return false; + visited[i] = true; + for (vector<int>::iterator vit = adjlist[i].begin(); vit != adjlist[i].end(); vit++) { + if (pairs[*vit] < 0 || dfs(pairs[*vit])) { + pairs[*vit] = i; pairs[i] = *vit; return true; + } + } + return false; +} + +int kuhn(int n, int m) { // n = nodes on left side (numbered 0..n-1), m = nodes on the right side + pairs.assign(n + m, -1); + int ans = 0; + for (int i = 0; i < n; i++) { + visited.assign(n + m, false); + ans += dfs(i); + } + return ans; //size of the MCBM +}
\ No newline at end of file Binary files differ |