blob: 655f5aa07d6edbf43499e96438631cf8867521a3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
struct edge {
int from, to;
ll cap;
};
vector<vector<edge>> adj, tmp;
vector<bool> erased;
void merge(int a, int b) {
tmp[a].insert(tmp[a].end(), all(tmp[b]));
tmp[b].clear();
erased[b] = true;
for (auto& v : tmp) {
for (auto&e : v) {
if (e.from == b) e.from = a;
if (e.to == b) e.to = a;
}}}
ll stoer_wagner() {
ll res = INF;
tmp = adj;
erased.assign(sz(tmp), false);
for (int i = 1; i < sz(tmp); i++) {
int s = 0;
while (erased[s]) s++;
priority_queue<pair<ll, int>> pq;
pq.push({0, s});
vector<ll> con(sz(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
con[c] = -1;
for (auto e : tmp[c]) {
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
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?!
merge(state.back().second, t);
res = min(res, state.back().first);
}
return res;
}
|
