diff options
Diffstat (limited to 'content/graph/stoerWagner.cpp')
| -rw-r--r-- | content/graph/stoerWagner.cpp | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index 97e667a..a122488 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -7,7 +7,7 @@ vector<vector<Edge>> adj, tmp; vector<bool> erased; void merge(int u, int v) { - tmp[u].insert(tmp[u].end(), all(tmp[v])); + tmp[u].insert(end(tmp[u]), begin(tmp[v]), end(tmp[v])); tmp[v].clear(); erased[v] = true; for (auto& vec : tmp) { @@ -19,33 +19,33 @@ void merge(int u, int v) { ll stoer_wagner() { ll res = INF; tmp = adj; - erased.assign(sz(tmp), false); - for (int i = 1; i < sz(tmp); i++) { + erased.assign(ssize(tmp), false); + for (int i = 1; i < ssize(tmp); i++) { int s = 0; while (erased[s]) s++; priority_queue<pair<ll, int>> pq; pq.push({0, s}); - vector<ll> con(sz(tmp)); + vector<ll> con(ssize(tmp)); ll cur = 0; vector<pair<ll, int>> state; while (!pq.empty()) { int c = pq.top().second; pq.pop(); - if (con[c] < 0) continue; //already seen + if (con[c] < 0) continue; // already seen con[c] = -1; for (auto e : tmp[c]) { - if (con[e.to] >= 0) {//add edge to cut + if (con[e.to] >= 0) { // add edge to cut con[e.to] += e.cap; pq.push({con[e.to], e.to}); cur += e.cap; - } else if (e.to != c) {//remove edge from cut + } else if (e.to != c) { // remove edge from cut cur -= e.cap; }} state.push_back({cur, c}); } int t = state.back().second; state.pop_back(); - if (state.empty()) return 0; //graph is not connected?! + if (state.empty()) return 0; // graph is not connected?! merge(state.back().second, t); res = min(res, state.back().first); } |