Min-Cut Max-Flow Theorem

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Edge {
5
    int to, rev;
6
    long long cap;
7
};
8
9
struct MaxFlowEK {
10
    int n; int s, t;
11
    vector<vector<Edge>> g;
12
    MaxFlowEK(int n, int s, int t) : n(n), s(s), t(t), g(n) {}
13
14
    void add_edge(int u, int v, long long c) {
15
        Edge a{v, (int)g[v].size(), c};
16
        Edge b{u, (int)g[u].size(), 0}; // reverse edge with 0 initial capacity
17
        g[u].push_back(a);
18
        g[v].push_back(b);
19
    }
20
21
    // BFS to find shortest augmenting path and store parent edge indices
22
    long long bfs(vector<pair<int,int>> &parent) {
23
        fill(parent.begin(), parent.end(), make_pair(-1, -1));
24
        queue<int> q; q.push(s); parent[s] = {s, -1};
25
        while (!q.empty()) {
26
            int u = q.front(); q.pop();
27
            for (int i = 0; i < (int)g[u].size(); ++i) {
28
                const Edge &e = g[u][i];
29
                if (parent[e.to].first == -1 && e.cap > 0) {
30
                    parent[e.to] = {u, i};
31
                    if (e.to == t) { // found path to sink; compute bottleneck
32
                        long long bottleneck = LLONG_MAX;
33
                        int v = t;
34
                        while (v != s) {
35
                            auto [pu, ei] = parent[v];
36
                            bottleneck = min(bottleneck, g[pu][ei].cap);
37
                            v = pu;
38
                        }
39
                        // augment along path
40
                        v = t;
41
                        while (v != s) {
42
                            auto [pu, ei] = parent[v];
43
                            Edge &e1 = g[pu][ei];
44
                            Edge &e2 = g[v][e1.rev];
45
                            e1.cap -= bottleneck; // use capacity
46
                            e2.cap += bottleneck; // add to reverse residual
47
                            v = pu;
48
                        }
49
                        return bottleneck;
50
                    }
51
                    q.push(e.to);
52
                }
53
            }
54
        }
55
        return 0; // no augmenting path
56
    }
57
58
    long long max_flow() {
59
        long long flow = 0;
60
        vector<pair<int,int>> parent(n);
61
        while (true) {
62
            long long pushed = bfs(parent);
63
            if (pushed == 0) break;
64
            flow += pushed;
65
        }
66
        return flow;
67
    }
68
69
    // After max_flow(), find vertices reachable from s in residual graph
70
    vector<int> min_cut_side_S() {
71
        vector<int> vis(n, 0);
72
        queue<int> q; q.push(s); vis[s] = 1;
73
        while (!q.empty()) {
74
            int u = q.front(); q.pop();
75
            for (const auto &e : g[u]) if (!vis[e.to] && e.cap > 0) {
76
                vis[e.to] = 1; q.push(e.to);
77
            }
78
        }
79
        return vis; // vis[v]==1 means v in S; else in T
80
    }
81
};
82
83
int main() {
84
    ios::sync_with_stdio(false);
85
    cin.tie(nullptr);
86
87
    // Example: simple graph
88
    // 0=s, 3=t
89
    // Edges: 0->1(3), 0->2(2), 1->2(1), 1->3(2), 2->3(4)
90
    int n = 4, s = 0, t = 3;
91
    MaxFlowEK mf(n, s, t);
92
    mf.add_edge(0, 1, 3);
93
    mf.add_edge(0, 2, 2);
94
    mf.add_edge(1, 2, 1);
95
    mf.add_edge(1, 3, 2);
96
    mf.add_edge(2, 3, 4);
97
98
    long long maxflow = mf.max_flow();
99
    cout << "Max flow = " << maxflow << "\n";
100
101
    // Extract min cut
102
    vector<int> S = mf.min_cut_side_S();
103
    long long cutCap = 0;
104
    vector<pair<int,int>> cutEdges;
105
    for (int u = 0; u < n; ++u) if (S[u]) {
106
        for (const auto &e : mf.g[u]) {
107
            // Original edge capacity equals reverse residual after max flow
108
            // But we didn't store originals; instead, detect S->T edges that are saturated: residual cap == 0 but existed originally
109
            // Here we approximate by checking that there is a reverse edge with positive capacity meaning some original existed.
110
            // Safer approach: track additions separately; for demo, identify S->T edges with zero residual.
111
            if (!S[e.to]) {
112
                // The residual capacity on forward edge is e.cap; if 0, edge is saturated and contributes to cut
113
                if (e.cap == 0) { cutCap += 0; /* capacity unknown here */ }
114
                // To report exact cut edges with capacities, track original capacity when adding edges in practice.
115
            }
116
        }
117
    }
118
119
    // To compute exact cut capacity, recompute by summing capacities of original S->T edges.
120
    // For this demo, we print S/T partition and note that maxflow equals min-cut capacity.
121
    cout << "S side: ";
122
    for (int i = 0; i < n; ++i) if (S[i]) cout << i << ' ';
123
    cout << "\nT side: ";
124
    for (int i = 0; i < n; ++i) if (!S[i]) cout << i << ' ';
125
    cout << "\nBy theorem, min cut capacity = max flow = " << maxflow << "\n";
126
    return 0;
127
}
128

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Edge {
5
    int to, rev;
6
    long long cap, orig_cap;
7
};
8
9
struct Dinic {
10
    int n, s, t;
11
    vector<vector<Edge>> g;
12
    vector<int> level, it;
13
    Dinic(int n, int s, int t) : n(n), s(s), t(t), g(n), level(n), it(n) {}
14
15
    void add_edge(int u, int v, long long c) {
16
        Edge a{v, (int)g[v].size(), c, c};
17
        Edge b{u, (int)g[u].size(), 0, 0};
18
        g[u].push_back(a);
19
        g[v].push_back(b);
20
    }
21
22
    bool bfs() {
23
        fill(level.begin(), level.end(), -1);
24
        queue<int> q; level[s] = 0; q.push(s);
25
        while (!q.empty()) {
26
            int u = q.front(); q.pop();
27
            for (const auto &e : g[u]) if (e.cap > 0 && level[e.to] == -1) {
28
                level[e.to] = level[u] + 1; q.push(e.to);
29
            }
30
        }
31
        return level[t] != -1;
32
    }
33
34
    long long dfs(int u, long long f) {
35
        if (u == t || f == 0) return f;
36
        for (int &i = it[u]; i < (int)g[u].size(); ++i) {
37
            Edge &e = g[u][i];
38
            if (e.cap > 0 && level[e.to] == level[u] + 1) {
39
                long long pushed = dfs(e.to, min(f, e.cap));
40
                if (pushed) {
41
                    e.cap -= pushed;
42
                    g[e.to][e.rev].cap += pushed;
43
                    return pushed;
44
                }
45
            }
46
        }
47
        return 0;
48
    }
49
50
    long long max_flow() {
51
        long long flow = 0;
52
        while (bfs()) {
53
            fill(it.begin(), it.end(), 0);
54
            while (long long pushed = dfs(s, LLONG_MAX)) flow += pushed;
55
        }
56
        return flow;
57
    }
58
59
    vector<int> min_cut_side_S() {
60
        vector<int> vis(n, 0);
61
        queue<int> q; q.push(s); vis[s] = 1;
62
        while (!q.empty()) {
63
            int u = q.front(); q.pop();
64
            for (const auto &e : g[u]) if (!vis[e.to] && e.cap > 0) {
65
                vis[e.to] = 1; q.push(e.to);
66
            }
67
        }
68
        return vis;
69
    }
70
};
71
72
int main() {
73
    ios::sync_with_stdio(false);
74
    cin.tie(nullptr);
75
76
    // Build a graph and compute max flow and exact min cut edges
77
    int n = 6, s = 0, t = 5;
78
    Dinic D(n, s, t);
79
    auto add = [&](int u, int v, long long c){ D.add_edge(u, v, c); };
80
    add(0,1,10); add(0,2,5); add(1,2,15);
81
    add(1,3,10); add(2,4,8); add(3,4,15);
82
    add(3,5,10); add(4,5,10);
83
84
    long long flow = D.max_flow();
85
    cout << "Max flow = " << flow << "\n";
86
87
    vector<int> S = D.min_cut_side_S();
88
    long long cutCap = 0;
89
    vector<tuple<int,int,long long>> cutEdges;
90
    for (int u = 0; u < n; ++u) if (S[u]) {
91
        for (const auto &e : D.g[u]) if (!S[e.to] && e.orig_cap > 0) {
92
            // Edge from S to T in original graph. If residual cap == 0, it's saturated, but any S->T edge contributes its original capacity to c(S,T).
93
            cutCap += e.orig_cap;
94
            cutEdges.emplace_back(u, e.to, e.orig_cap);
95
        }
96
    }
97
98
    cout << "Min cut capacity = " << cutCap << "\nEdges in one min cut (S->T):\n";
99
    for (auto [u,v,c] : cutEdges) cout << u << " -> " << v << " (cap=" << c << ")\n";
100
101
    return 0;
102
}
103

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Solve: Given n projects with weight w[i] (profit can be negative = cost), and prerequisites i -> j (to take j, must take i).
5
// Build a flow network and compute the max-weight feasible subset. Standard reduction:
6
// - For w[i] > 0: add edge S->i with capacity w[i].
7
// - For w[i] < 0: add edge i->T with capacity -w[i].
8
// - For prerequisite i->j: add edge i->j with INF (force closure: if j in S-side, i must be too).
9
// Answer: max_weight = sum_pos - mincut(S, T). Chosen set = vertices reachable from S in residual graph.
10
11
struct Edge { int to, rev; long long cap; };
12
struct Dinic {
13
    int n, s, t; vector<vector<Edge>> g; vector<int> level, it;
14
    Dinic(int n, int s, int t): n(n), s(s), t(t), g(n), level(n), it(n) {}
15
    void add_edge(int u, int v, long long c) { Edge a{v,(int)g[v].size(),c}; Edge b{u,(int)g[u].size(),0}; g[u].push_back(a); g[v].push_back(b);}    
16
    bool bfs(){ fill(level.begin(),level.end(),-1); queue<int>q; level[s]=0; q.push(s); while(!q.empty()){int u=q.front(); q.pop(); for(auto &e:g[u]) if(e.cap>0 && level[e.to]==-1){ level[e.to]=level[u]+1; q.push(e.to);} } return level[t]!=-1; }
17
    long long dfs(int u, long long f){ if(u==t||f==0) return f; for(int &i=it[u]; i<(int)g[u].size(); ++i){ auto &e=g[u][i]; if(e.cap>0 && level[e.to]==level[u]+1){ long long pushed=dfs(e.to, min(f,e.cap)); if(pushed){ e.cap-=pushed; g[e.to][e.rev].cap+=pushed; return pushed; } } } return 0; }
18
    long long max_flow(){ long long flow=0; while(bfs()){ fill(it.begin(),it.end(),0); while(long long pushed=dfs(s,LLONG_MAX)) flow+=pushed; } return flow; }
19
    vector<int> reachable_from_s(){ vector<int> vis(n,0); queue<int>q; q.push(s); vis[s]=1; while(!q.empty()){int u=q.front(); q.pop(); for(auto &e:g[u]) if(e.cap>0 && !vis[e.to]){ vis[e.to]=1; q.push(e.to);} } return vis; }
20
};
21
22
int main(){
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
26
    // Example: 5 projects with weights, and prerequisites
27
    int n = 5; // projects 0..4
28
    vector<long long> w = {5, -3, 4, -2, 6};
29
    vector<pair<int,int>> prereq = {{0,2}, {2,4}}; // 0->2, 2->4
30
31
    int S = n, T = n+1; long long INF = (long long)4e18;
32
    Dinic D(n+2, S, T);
33
34
    long long sumPos = 0;
35
    for(int i=0;i<n;++i){
36
        if(w[i] > 0){ D.add_edge(S,i,w[i]); sumPos += w[i]; }
37
        else if(w[i] < 0){ D.add_edge(i,T,-w[i]); }
38
    }
39
    for(auto [u,v]: prereq){
40
        D.add_edge(u, v, INF); // if v is chosen (in S-side), u must be too
41
    }
42
43
    long long mincut = D.max_flow();
44
    vector<int> Sside = D.reachable_from_s();
45
46
    long long maxWeight = sumPos - mincut;
47
    cout << "Max total weight = " << maxWeight << "\nChosen projects: ";
48
    for(int i=0;i<n;++i) if(Sside[i]) cout << i << ' ';
49
    cout << "\n";
50
    return 0;
51
}
52