merge mzuenni changesHEADmaster

7 files changed, 12 insertions, 12 deletions

diff --git a/content/geometry/formulas.cpp b/content/geometry/formulas.cpp
index b339451..cb4be45 100644
--- a/content/geometry/formulas.cpp
+++ b/content/geometry/formulas.cpp
@@ -21,7 +21,7 @@ auto cross(pt p, pt a, pt b) { return cross(a - p, b - p); }
 //  1 => c links von a->b
 //  0 => a, b und c kolliniear
 // -1 => c rechts von a->b
-int ccw(pt a, pt b, pt c) {
+ll ccw(pt a, pt b, pt c) {
 	auto orien = cross(b - a, c - a);
 	return (orien > EPS) - (orien < -EPS);
 }
diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index b27db0b..040cf3b 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -248,14 +248,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 
 \subsubsection{\textsc{Dinitz}'s Algorithm mit Capacity Scaling}
 \begin{methods}
-	\method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}}
+	\method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\min(\abs{V}^2\cdot\abs{E}, F\cdot\abs{E})}
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
 \sourcecode{graph/dinitzScaling.cpp}
 
 \begin{algorithm}{Min-Cost-Max-Flow}
 	\begin{methods}
-		\method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2}
+		\method{mincostflow}{berechnet Fluss}{F\cdot\abs{V}\cdot\abs{E}}
 	\end{methods}
 	\sourcecode{graph/minCostMaxFlow.cpp}
 \end{algorithm}
diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp
index a122488..c28800e 100644
--- a/content/graph/stoerWagner.cpp
+++ b/content/graph/stoerWagner.cpp
@@ -44,10 +44,10 @@ ll stoer_wagner() {
 			state.push_back({cur, c});
 		}
 		int t = state.back().second;
-		state.pop_back();
+		state.pop_back(); // cut between comp(t) and everything else
 		if (state.empty()) return 0; // graph is not connected?!
-		merge(state.back().second, t);
 		res = min(res, state.back().first);
+		merge(state.back().second, t);
 	}
 	return res;
 }
diff --git a/content/math/legendre.cpp b/content/math/legendre.cpp
index b85ea2a..80825ea 100644
--- a/content/math/legendre.cpp
+++ b/content/math/legendre.cpp
@@ -1,4 +1,4 @@
-ll legendre(ll a, ll p) { // p prim >= 2
+ll legendreS(ll a, ll p) { // p prim >= 2
 	ll s = powMod(a, p / 2, p);
 	return s < 2 ? s : -1ll;
 }
diff --git a/content/math/sqrtModCipolla.cpp b/content/math/sqrtModCipolla.cpp
index c062646..a65e84c 100644
--- a/content/math/sqrtModCipolla.cpp
+++ b/content/math/sqrtModCipolla.cpp
@@ -1,7 +1,7 @@
-ll sqrtMod(ll a, ll p) {// teste mit Legendre ob Lösung existiert
+ll sqrtMod(ll a, ll p) { // teste mit legendreS ob lösung existiert
 	if (a < 2) return a;
 	ll t = 0;
-	while (legendre((t*t-4*a) % p, p) >= 0) t = rng() % p;
+	while (legendreS((t*t-4*a) % p, p) >= 0) t = rng() % p;
 	ll b = -t, c = -t, d = 1, m = p;
 	for (m++; m /= 2; b = (a+a-b*b) % p, a = (a*a) % p) {
 		if (m % 2) {
diff --git a/test/math/legendre.cpp b/test/math/legendre.cpp
index 44f88c1..c828302 100644
--- a/test/math/legendre.cpp
+++ b/test/math/legendre.cpp
@@ -11,7 +11,7 @@ void stress_test() {
 		vector<bool> isSquare(p);
 		for (ll j = 1; j < p; j++) isSquare[(j*j) % p] = true;
 		for (ll j = 0; j < p; j++) {			
-			auto got = legendre(j, p);
+			auto got = legendreS(j, p);
 			auto expected = j == 0 ? 0 : (isSquare[j] ? 1 : -1);
 			if (got != expected) cerr << "error: " << j << " " << p << FAIL;
 		}
@@ -28,7 +28,7 @@ void performance_test() {
 	for (int operations = 0; operations < N; operations++) {
 		ll j = Random::integer<ll>(mod);
 		t.start();
-		hash += legendre(j, mod);
+		hash += legendreS(j, mod);
 		t.stop();
 	}
 	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
diff --git a/test/math/sqrtModCipolla.cpp b/test/math/sqrtModCipolla.cpp
index c7be9a4..0d7de70 100644
--- a/test/math/sqrtModCipolla.cpp
+++ b/test/math/sqrtModCipolla.cpp
@@ -10,7 +10,7 @@ void stress_test(ll range) {
 		ll p = Random::prime<ll>(range);
 		for (ll j = 0; j < 100; j++) {
 			ll x = Random::integer<ll>(0, p);
-			if (legendre(x, p) < 0) continue;
+			if (legendreS(x, p) < 0) continue;
 
 			ll got = sqrtMod(x, p);
 			if (got < 0 || got >= p) cerr << "error: out of range" << FAIL;
@@ -30,7 +30,7 @@ void performance_test() {
 		ll x;
 		do {
 			x = Random::integer<ll>(0, mod);
-		} while (legendre(x, mod) >= 0);
+		} while (legendreS(x, mod) >= 0);
 		t.start();
 		hash += sqrtMod(x, mod);
 		t.stop();