Tìm cắt s-t tối thiểu trong mạng luồng trong C++

Cho mạng luồng. Cắt s-t yêu cầu nguồn s và giếng t ở hai tập con khác nhau, bao gồm các cạnh từ tập nguồn đến tập giếng. Dung lượng cắt là tổng dung lượng các cạnh trong tập cắt. Tìm cắt s-t có dung lượng tối thiểu, in ra các cạnh của cắt tối thiểu.

Ví dụ: Đồ thị 6 nút, đầu ra các cạnh cắt tối thiểu: (1,3), (4,3), (4,5).

Thuật toán (Edmonds-Karp / Ford-Fulkerson + DFS)

• Dùng BFS tìm đường tăng luồng (augmenting path) trong đồ thị còn dư.
• Cập nhật luồng trên đường tìm được.
• Lặp cho đến khi không còn đường tăng.
• Sau khi tìm luồng tối đa, dùng DFS từ nguồn trên đồ thị còn dư để tìm các nút đạt được.
• Các cạnh từ nút đạt được đến nút không đạt được trong đồ thị gốc là cắt tối thiểu.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

#define NODES 6

int bfs(int graph[NODES][NODES], int src, int sink, int par[]) {
    bool vis[NODES];
    memset(vis, 0, sizeof(vis));
    queue<int> que;
    que.push(src);
    vis[src] = true;
    par[src] = -1;
    while (!que.empty()) {
        int u1 = que.front(); que.pop();
        for (int v1 = 0; v1 < NODES; v1++) {
            if (!vis[v1] && graph[u1][v1] > 0) {
                que.push(v1);
                par[v1] = u1;
                vis[v1] = true;
            }
        }
    }
    return vis[sink];
}

void dfs(int graph[NODES][NODES], int src, bool vis[]) {
    vis[src] = true;
    for (int i = 0; i < NODES; i++)
        if (graph[src][i] && !vis[i])
            dfs(graph, i, vis);
}

void minCut(int graph[NODES][NODES], int src, int sink) {
    int u, v;
    int temp_graph[NODES][NODES];
    for (u = 0; u < NODES; u++)
        for (v = 0; v < NODES; v++)
            temp_graph[u][v] = graph[u][v];
    int par[NODES];
    while (bfs(temp_graph, src, sink, par)) {
        int path_flow = INT_MAX;
        for (v = sink; v != src; v = par[v]) {
            u = par[v];
            path_flow = min(path_flow, temp_graph[u][v]);
        }
        for (v = sink; v != src; v = par[v]) {
            u = par[v];
            temp_graph[u][v] -= path_flow;
            temp_graph[v][u] += path_flow;
        }
    }
    bool vis[NODES];
    memset(vis, false, sizeof(vis));
    dfs(temp_graph, src, vis);
    for (int i = 0; i < NODES; i++)
        for (int j = 0; j < NODES; j++)
            if (vis[i] && !vis[j] && graph[i][j])
                cout << "(" << i << ", " << j << ")" << endl;
}

int main() {
    int graph1[NODES][NODES] = {
        {0, 17, 14, 0, 0, 0},
        {0, 0, 11, 13, 0, 0},
        {0, 5, 0, 0, 15, 0},
        {0, 0, 9, 0, 0, 21},
        {0, 0, 0, 8, 0, 5},
        {0, 0, 0, 0, 0, 0}
    };
    minCut(graph1, 0, 5);
}

Đầu ra

(1, 3)
(4, 3)
(4, 5)