From e47c57a92d07f40d792b4a22c9934e0502c75aad Mon Sep 17 00:00:00 2001 From: Syndamia Date: Sun, 21 May 2023 20:14:51 +0300 Subject: [DAAP] Added exercises from second exam --- .../Practicum/Exam2/2-Interstellar.cpp | 60 ++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp (limited to 'Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp') diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp new file mode 100644 index 0000000..4ea0d35 --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp @@ -0,0 +1,60 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +/* + * 6 <-- 11 -- 7 + * 7 <-- 19 -- 6 + * -- -19 -> 6 + * + */ + +bool topo(long long c, long long& temp, vector>>& graph, vector& mark) { + if (mark[c] == 2) return true; + if (mark[c] == 1) return false; + mark[c] = 1; + for (pair& p : graph[c]) { + if (p.second < 0) continue; + bool res = topo(p.first, temp, graph, mark); + if (!res && temp < p.second) { + mark[c] = 0; + p.second *= -1; + for (pair& pa : graph[p.first]) { + if (pa.first == c) { + pa.second *= -1; + break; + } + } + res = topo(p.first, temp, graph, mark); + if (!res) return false; + } + } + mark[c] = 2; + return true; +} + +int main() { + ios::sync_with_stdio(false); + cin.tie(NULL); + cout.tie(NULL); + + long long N, M; + cin >> N >> M; + vector>> graph(N+1, vector>()); + for (long long i = 0; i < M; i++) { + long long ai, bi, ci; + cin >> ai >> bi >> ci; + graph[bi].push_back({ ai, ci }); + graph[ai].push_back({ -bi, ci }); + } + for (long long t = 0; t < 20; t++) { + vector mark(N+1); + if (topo(1, t, graph, mark)) { + cout << t << endl; + } + } +} -- cgit v1.3.1-26-gb76a