Graph/MaxFlow/MinimumCut.h

View this file on GitHub
Last update: 2022-11-26 11:47:19+08:00

Code

// Minimum cut between every pair of vertices (Stoer Wagner)
pair<int, vector<int>> GetMinCut(const vector<vector<int>> &weights) {
    int N = weights.size();
    vector<int> used(N), cut, best_cut;
    int best_weight = -1;
    
    for (int phase = N-1; phase >= 0; phase--) {
        vector<int> w = weights[0];
        vector<int> 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);
}

#line 1 "Graph/MaxFlow/MinimumCut.h"
// Minimum cut between every pair of vertices (Stoer Wagner)
pair<int, vector<int>> GetMinCut(const vector<vector<int>> &weights) {
    int N = weights.size();
    vector<int> used(N), cut, best_cut;
    int best_weight = -1;
    
    for (int phase = N-1; phase >= 0; phase--) {
        vector<int> w = weights[0];
        vector<int> 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);
}