diff options
| -rw-r--r-- | sonstiges/2sat.cpp | 63 | ||||
| -rw-r--r-- | sonstiges/sonstiges.tex | 4 | ||||
| -rw-r--r-- | tcr.pdf | bin | 45111 -> 81835 bytes | |||
| -rw-r--r-- | tcr.tex | 34 |
4 files changed, 88 insertions, 13 deletions
diff --git a/sonstiges/2sat.cpp b/sonstiges/2sat.cpp new file mode 100644 index 0000000..627e484 --- /dev/null +++ b/sonstiges/2sat.cpp @@ -0,0 +1,63 @@ +vector< vector<int> > adjlist; //adjazenzliste +vector<int> sccs; //speichert die gefundenen SCCs +vector<bool> visited; //welcher Knoten ist schon besucht worden (in der DFS) +vector<bool> inStack; //ist Knoten gerade im Stack +vector<int> d; //discovery time +vector<int> low; //wie weit hoch geht's im Tiefensuchbaum +int counter; //Zaehler fuer discovery time +stack<int> st; //der Stack +int sccCounter; //Zaehler fuer SCCs + +//Tiefensuche, die starke Zusammenhangskomponenten findet +void visit(int v) { + visited[v] = true; + d[v] = counter; + low[v] = counter; + counter++; + st.push(v); + inStack[v] = true; + + for (int i = 0; i < (int)adjlist[v].size(); i++) { + int w = adjlist[v][i]; + + if (!visited[w]) { + visit(w); + low[v] = min(low[v], low[w]); + } else if (inStack[w]) { + low[v] = min(low[v], low[w]); + } + } + + if (low[v] == d[v]) { + int next; + do { + next = st.top(); + st.pop(); + sccs[next] = sccCounter; + inStack[next] = false; + } while (next != v); + + sccCounter++; + } +} + +void solve() { + //adjlist initialisieren + //(a || b) wird zu (!a => b) und (!b => a) + + visited.clear(); visited.assign(adjlist.size(), false); + inStack.clear(); inStack.assign(adjlist.size(), false); + d.clear(); d.assign(adjlist.size(), false); + low.clear(); low.assign(adjlist.size(), false); + sccs.clear(); sccs.resize(adjlist.size()); + + counter = 0; + sccCounter = 0; + for (i = 0; i < (int)adjlist.size(); i++) { + if (!visited[i]) { + visit(i); + sccCounter++; + } + } + // genau dann loesbar, wenn keine Variable in gleicher SCC wie Negation ist +}
\ No newline at end of file diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex new file mode 100644 index 0000000..0befff3 --- /dev/null +++ b/sonstiges/sonstiges.tex @@ -0,0 +1,4 @@ +\section{Sonstiges} + +\subsection{2-SAT} +\lstinputlisting{sonstiges/2sat.cpp}
\ No newline at end of file Binary files differ@@ -18,19 +18,19 @@ \usepackage{listings} \lstset{ language={C++}, - numbers=left, - stepnumber=1, - numbersep=6pt, - numberstyle=\footnotesize, - breaklines=true, - breakautoindent=true, - breakatwhitespace=false, - postbreak=\space, - tabsize=2, - basicstyle=\ttfamily\footnotesize, - showspaces=false, - showstringspaces=false, - extendedchars=true, + numbers=left, + stepnumber=1, + numbersep=6pt, + numberstyle=\footnotesize, + breaklines=true, + breakautoindent=true, + breakatwhitespace=false, + postbreak=\space, + tabsize=2, + basicstyle=\ttfamily\footnotesize, + showspaces=false, + showstringspaces=false, + extendedchars=true, keywordstyle=\color{blue}\bfseries, stringstyle=\color{darkred}, commentstyle=\color{darkgreen} @@ -38,9 +38,17 @@ \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry} +\title{Team Contest Reference} +\author{ChaosKITs \\ Karlsruhe Institute of Technology} + \begin{document} +\maketitle +\tableofcontents +\newpage + \input{maxFlow/maxFlow} \input{geometry/geometry} +\input{sonstiges/sonstiges} \end{document}
\ No newline at end of file |