Commita990b25

authored

Merge branch 'main' into main

2 parentsfc498bc +4685762 commita990b25Copy full SHA for a990b25

File tree

+10

-13

lines changed

+10

-13

lines changed

Lines changed: 9 additions & 12 deletions

Original file line number	Diff line number	Diff line change
`@@ -30,50 +30,47 @@ Do $N$ iterations of Bellman-Ford algorithm. If there were no changes on the las`
`30`	`30`	`structEdge {`
`31`	`31`	`int a, b, cost;`
`32`	`32`	`};`
`33`		`-`
`34`		`-int n, m;`
	`33`	`+`
	`34`	`+int n;`
`35`	`35`	`vector<Edge> edges;`
`36`	`36`	`const int INF = 1000000000;`
`37`		`-`
	`37`	`+`
`38`	`38`	`void solve() {`
`39`		`- vector<int> d(n,INF);`
	`39`	`+ vector<int> d(n,0);`
`40`	`40`	`vector<int> p(n, -1);`
`41`	`41`	`int x;`
`42`		`-`
`43`		`- d[0] = 0;`
`44`		`-`
	`42`	`+`
`45`	`43`	`for (int i = 0; i < n; ++i) {`
`46`	`44`	`x = -1;`
`47`	`45`	`for (Edge e : edges) {`
`48`		`- if (d[e.a]< INF && d[e.a]+ e.cost < d[e.b]) {`
	`46`	`+ if (d[e.a] + e.cost < d[e.b]) {`
`49`	`47`	`d[e.b] = max(-INF, d[e.a] + e.cost);`
`50`	`48`	`p[e.b] = e.a;`
`51`	`49`	`x = e.b;`
`52`	`50`	`}`
`53`	`51`	`}`
`54`	`52`	`}`
`55`		`-`
	`53`	`+`
`56`	`54`	`if (x == -1) {`
`57`	`55`	`cout << "No negative cycle found.";`
`58`	`56`	`} else {`
`59`	`57`	`for (int i = 0; i < n; ++i)`
`60`	`58`	`x = p[x];`
`61`		`-`
	`59`	`+`
`62`	`60`	`vector<int> cycle;`
`63`	`61`	`for (int v = x;; v = p[v]) {`
`64`	`62`	`cycle.push_back(v);`
`65`	`63`	`if (v == x && cycle.size() > 1)`
`66`	`64`	`break;`
`67`	`65`	`}`
`68`	`66`	`reverse(cycle.begin(), cycle.end());`
`69`		`-`
	`67`	`+`
`70`	`68`	`cout << "Negative cycle: ";`
`71`	`69`	`for (int v : cycle)`
`72`	`70`	`cout << v << ' ';`
`73`	`71`	`cout << endl;`
`74`	`72`	`}`
`75`	`73`	`}`
`76`		`-`
`77`	`74`	```
`78`	`75`
`79`	`76`	`##Using Floyd-Warshall algorithm`

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -68,7 +68,7 @@ T order_statistics (std::vector<T> a, unsigned n, unsigned k)`
`68`	`68`
`69`	`69`	`## Notes`
`70`	`70`	`* The randomized algorithm above is named [quickselect](https://en.wikipedia.org/wiki/Quickselect). You should do random shuffle on $A$ before calling it or use a random element as a barrier for it to run properly. There are also deterministic algorithms that solve the specified problem in linear time, such as [median of medians](https://en.wikipedia.org/wiki/Median_of_medians).`
`71`		`-*A deterministic linear solution is implemented in C++ standard library as[std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element).`
	`71`	`+* [std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element) solves this in C++ but gcc's implementation runs in worst case $O(n \log n )$ time.`
`72`	`72`	`* Finding $K$ smallest elements can be reduced to finding $K$-th element with a linear overhead, as they're exactly the elements that are smaller than $K$-th.`
`73`	`73`
`74`	`74`	`## Practice Problems`

Comments

(0)