From 1d938c77d5235ac9b04095114d316b8bef7ac8a3 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:10:54 +0100 Subject: Added LCA, tested on icpc prob. --- graph/LCA.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) create mode 100644 graph/LCA.cpp diff --git a/graph/LCA.cpp b/graph/LCA.cpp new file mode 100644 index 0000000..d252bac --- /dev/null +++ b/graph/LCA.cpp @@ -0,0 +1,16 @@ +//RMQ muss hinzugefügt werden! +vector visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); +vector> graph(MAX_N); + +void initLCA(int gi, int d, int &c) { + visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++; + for(int gn : graph[gi]) { + initLCA(gn, d+1, c); + visited[c] = gi, depth[c] = d, c++; + } +} +//[a, b] +int getLCA(int a, int b) { + return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))]; +} +//=> int c = 0; initLCA(0,0,c); initRMQ(); done! -- cgit v1.2.3 From 3e14dcd6c67c80b4cbc5c7e949a25fe20dc676e2 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:12:51 +0100 Subject: Update graph.tex --- graph/graph.tex | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/graph/graph.tex b/graph/graph.tex index fada803..b35adc4 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,5 +1,8 @@ \section{Graphen} +\subsection{Lowest Common Ancestor} +\lstinputlisting{graph/LCA.cpp} + \subsection{Kürzeste Wege} \subsubsection{Algorithmus von \textsc{Dijkstra}} @@ -26,4 +29,4 @@ Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \lstinputlisting{graph/euler.cpp} \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} -\lstinputlisting{graph/edmondsKarp.cpp} \ No newline at end of file +\lstinputlisting{graph/edmondsKarp.cpp} -- cgit v1.2.3 From 9753d518eb3204e380bdf4af24145166896bcf76 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:15:44 +0100 Subject: Create RMQ.cpp --- datastructures/RMQ.cpp | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 datastructures/RMQ.cpp diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp new file mode 100644 index 0000000..899db15 --- /dev/null +++ b/datastructures/RMQ.cpp @@ -0,0 +1,20 @@ +vector data(RMQ_SIZE); +vector> rmq(floor(log2(RMQ_SIZE)) + 1, vector(RMQ_SIZE)); + +void initRMQ() { + for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) { + for(int l = 0; l + s <= RMQ_SIZE; l++) { + if(i == 0) rmq[0][l] = l; + else { + int r = l + ss; + rmq[i][l] = (data[rmq[i-1][l]] <= data[rmq[i-1][r]] ? rmq[i-1][l] : rmq[i-1][r]); + } + } + } +} +//returns index of minimum! [a, b) +int queryRMQ(int l, int r) { + if(l >= r) return l; + int s = floor(log2(r-l)); r = r - (1 << s); + return (data[rmq[s][l]] <= data[rmq[s][r]] ? rmq[s][l] : rmq[s][r]); +} -- cgit v1.2.3 From 213662f659ed8b0a95da110ae6eb5e91e2ecae71 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Sat, 22 Nov 2014 20:16:34 +0100 Subject: added RMQ. --- datastructures/datastructures.tex | 3 +++ 1 file changed, 3 insertions(+) diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index c314400..baa4fec 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -5,3 +5,6 @@ \subsection{Segmentbaum} \lstinputlisting{datastructures/segmentTree.cpp} + +\subsection{Range Minimum Query} +\lstinputlisting{datastructures/RMQ.cpp} -- cgit v1.2.3 From 4cc304e57566d149582d974cdaf4a7f724c6b5c1 Mon Sep 17 00:00:00 2001 From: pjungeblut Date: Sun, 23 Nov 2014 22:59:10 +0100 Subject: Floyd Warshall --- graph/floydWarshall.cpp | 8 ++++++++ graph/graph.tex | 4 ++++ tcr.pdf | Bin 170218 -> 172571 bytes 3 files changed, 12 insertions(+) create mode 100644 graph/floydWarshall.cpp diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp new file mode 100644 index 0000000..ee56441 --- /dev/null +++ b/graph/floydWarshall.cpp @@ -0,0 +1,8 @@ +//initialize adjmat, adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j +for (k = 0; k < MAX_V; k++) { + for (i = 0; i < MAX_V; i++) { + for (j = 0; j < MAX_V; j++) { + if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j]; + } + } +} \ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 2bf395c..8d01e97 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -10,6 +10,10 @@ Kürzeste Pfade in Graphen ohne negative Kanten. Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \lstinputlisting{graph/bellmannFord.cpp} +\subsubsection{\textsc{Floyd-Warshall}-Algorithmus} +Alle kürzesten Pfade im Graphen. +\lstinputlisting{graph/floydWarshall.cpp} + \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} diff --git a/tcr.pdf b/tcr.pdf index 07e4ceb..af23bcc 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3