123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 |
- // Adjacency matrix implementation of Stoer-Wagner min cut algorithm.
- //
- // Running time:
- // O(|V|^3)
- //
- // INPUT:
- // - graph, constructed using AddEdge()
- //
- // OUTPUT:
- // - (min cut value, nodes in half of min cut)
- #include <cmath>
- #include <vector>
- #include <iostream>
- using namespace std;
- typedef vector<int> VI;
- typedef vector<VI> VVI;
- const int INF = 1000000000;
- pair<int, VI> GetMinCut(VVI &weights) {
- int N = weights.size();
- VI used(N), cut, best_cut;
- int best_weight = -1;
-
- for (int phase = N-1; phase >= 0; phase--) {
- VI w = weights[0];
- VI added = used;
- int prev, last = 0;
- for (int i = 0; i < phase; i++) {
- prev = last;
- last = -1;
- for (int j = 1; j < N; j++)
- if (!added[j] && (last == -1 || w[j] > w[last])) last = j;
- if (i == phase-1) {
- for (int j = 0; j < N; j++) weights[prev][j] += weights[last][j];
- for (int j = 0; j < N; j++) weights[j][prev] = weights[prev][j];
- used[last] = true;
- cut.push_back(last);
- if (best_weight == -1 || w[last] < best_weight) {
- best_cut = cut;
- best_weight = w[last];
- }
- } else {
- for (int j = 0; j < N; j++)
- w[j] += weights[last][j];
- added[last] = true;
- }
- }
- }
- return make_pair(best_weight, best_cut);
- }
|