diff options
| -rw-r--r-- | graph/bellmannFord.cpp | 18 | ||||
| -rw-r--r-- | graph/graph.tex | 5 | ||||
| -rw-r--r-- | math/extendedEuclid.cpp | 11 | ||||
| -rw-r--r-- | math/gcd-lcm.cpp | 7 | ||||
| -rw-r--r-- | math/math.tex | 4 | ||||
| -rw-r--r-- | tcr.pdf | bin | 220754 -> 237903 bytes |
6 files changed, 45 insertions, 0 deletions
diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp new file mode 100644 index 0000000..94fa034 --- /dev/null +++ b/graph/bellmannFord.cpp @@ -0,0 +1,18 @@ +//n = number of vertices, edges is vector of edges +dist.assign(n, INF); dist[0] = 0; +parent.assign(n, -1); +for (i = 0; i < n - 1; i++) { + for (j = 0; j < (int)edges.size(); j++) { + if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + dist[edges[j].to] = dist[edges[j].from] + edges[j].cost; + parent[edges[j].to] = edges[j].from; + } + } +} +//now dist and parent are correct shortest paths +//next lines check for negative cycles +for (j = 0; j < (int)edges.size(); j++) { + if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + //NEGATIVE CYCLE found + } +} diff --git a/graph/graph.tex b/graph/graph.tex index 53cfb2a..4646ee3 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,5 +1,10 @@ \section{Graphen} +\subsection{Kürzeste Wege} + +\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +\lstinputlisting{graph/bellmannFord.cpp} + \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp new file mode 100644 index 0000000..6d9490f --- /dev/null +++ b/math/extendedEuclid.cpp @@ -0,0 +1,11 @@ +//Accepted in Aufgabe mit Forderung: |X|+|Y| minimal (primaer) und X<=Y (sekundaer) +//hab aber keinen Beweis dafuer :) +ll x, y, d; //a * x + b * y = d = ggT(a,b) +void extendedEuclid(ll a, ll b) { + if (!b) { + x = 1; y = 0; d = a; return; + } + extendedEuclid(b, a % b); + ll x1 = y; ll y1 = x - (a / b) * y; + x = x1; y = y1; +}
\ No newline at end of file diff --git a/math/gcd-lcm.cpp b/math/gcd-lcm.cpp new file mode 100644 index 0000000..3a0f742 --- /dev/null +++ b/math/gcd-lcm.cpp @@ -0,0 +1,7 @@ +ll gcd(ll a, ll b) { + return b == 0 ? a : gcd (b, a % b); +} + +ll lcm(ll a, ll b) { + return a * (b / gcd(a, b)); //Klammern gegen Overflow +}
\ No newline at end of file diff --git a/math/math.tex b/math/math.tex index e1e0950..0b66163 100644 --- a/math/math.tex +++ b/math/math.tex @@ -1,4 +1,8 @@ \section{Mathe} +\subsection{ggT, kgV, erweiterter euklidischer Algorithmus} +\lstinputlisting{math/gcd-lcm.cpp} +\lstinputlisting{math/extendedEuclid.cpp} + \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp}
\ No newline at end of file Binary files differ |