Dòng chảy trên đồ thị có hướng

Xét một đồ thị có hướng \( G = (V, E) \), trong đó mỗi cạnh được gán một giá trị gọi là dung lượng. Hai đỉnh đặc biệt \( S \) (nguồn) và \( T \) (đích) được xác định trước. Mục tiêu là tìm dòng chảy lớn nhất từ \( S \) đến \( T \) sao cho các điều kiện sau luôn được thỏa mãn:

• Giới hạn dung lượng: Dòng chảy \( f(u,v) \) trên cạnh \( (u,v) \) không vượt quá dung lượng \( c(u,v) \), tức là \( f(u,v) \leq c(u,v) \).
• Tính đối xứng nghịch đảo: \( f(u,v) = -f(v,u) \). Điều này giúp mô hình hóa việc "trả ngược" dòng chảy khi cần hiệu chỉnh.
• Bảo toàn dòng tại các đỉnh trung gian: Với mọi đỉnh \( u \ne S, u \ne T \), tổng dòng chảy vào bằng tổng dòng chảy ra: \[ \sum_{(v,u)\in E} f(v,u) = \sum_{(u,w)\in E} f(u,w) \]

Giá trị của dòng chảy toàn cục được tính bởi tổng dòng chảy rời khỏi nguồn: \( |f| = \sum_{(S,v)\in E} f(S,v) \). Bài toán dòng chảy tối đa yêu cầu tìm giá trị lớn nhất có thể đạt được của đại lượng này.

Thuật toán Edmonds-Karp (EK)

Thuật toán EK hoạt động bằng cách lặp lại việc tìm đường tăng – một đường đi từ \( S \) đến \( T \) trong mạng dư (residual network) – rồi đẩy thêm dòng dọc theo đường đó. Mỗi lần tăng sẽ cập nhật dòng chảy và mạng dư tương ứng.

Một kỹ thuật quan trọng là xây dựng cạnh nghịch với dung lượng 0 để cho phép "hoàn dòng" nếu phát hiện lựa chọn chưa tối ưu. Độ phức tạp thời gian là \( O(nm^2) \), tuy nhiên trong thực tế thường nhanh hơn nhiều, phù hợp với đồ thị cỡ \( 10^3 \sim 10^4 \) đỉnh/cạnh.

Thuật toán Dinic

Dinic cải tiến EK bằng cách phân lớp đồ thị (level graph) sử dụng BFS, sau đó dùng DFS để đẩy đồng thời nhiều đơn vị dòng chảy qua các đường cùng độ dài ngắn nhất. Thuật toán này áp dụng tối ưu hóa cung hiện tại (current arc optimization) nhằm tránh xét lại các cạnh đã bão hòa.

Độ phức tạp lý thuyết là \( O(n^2m) \), nhưng nhờ các tối ưu hóa, thực tế chạy rất nhanh, xử lý tốt mạng có tới \( 10^5 \) cạnh.

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

struct Edge {
    int to, next, cap;
};

vector<Edge> edges;
vector<int> head, level, current;
int n, m, source, sink;

void addEdge(int u, int v, int w) {
    edges.push_back({v, head[u], w});
    head[u] = edges.size() - 1;
    edges.push_back({u, head[v], 0});
    head[v] = edges.size() - 1;
}

bool bfs() {
    fill(level.begin(), level.end(), -1);
    queue<int> q;
    q.push(source);
    level[source] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (edges[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[sink] != -1;
}

long long dfs(int u, long long flow) {
    if (u == sink || flow == 0) return flow;
    long long totalFlow = 0;
    for (int& i = current[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        if (edges[i].cap > 0 && level[v] == level[u] + 1) {
            long long pushed = dfs(v, min(flow, (long long)edges[i].cap));
            if (pushed > 0) {
                edges[i].cap -= pushed;
                edges[i ^ 1].cap += pushed;
                totalFlow += pushed;
                flow -= pushed;
                if (flow == 0) break;
            }
        }
    }
    return totalFlow;
}

long long dinic() {
    long long maxFlow = 0;
    while (bfs()) {
        copy(head.begin(), head.end(), current.begin());
        maxFlow += dfs(source, LLONG_MAX);
    }
    return maxFlow;
}

int main() {
    cin >> n >> m >> source >> sink;
    head.assign(n + 1, -1);
    level.resize(n + 1);
    current.resize(n + 1);
    edges.reserve(2 * m);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);
    }

    cout << dinic() << endl;
    return 0;
}

Bài toán Cắt nhỏ nhất

Một cắt \( (S,T) \) là cách chia tập đỉnh thành hai phần rời nhau sao cho nguồn thuộc phần này, đích thuộc phần kia. Dung lượng của cắt là tổng dung lượng các cạnh từ phía chứa nguồn sang phía chứa đích.

Theo định lý Max-Flow Min-Cut, giá trị dòng chảy tối đa bằng đúng dung lượng nhỏ nhất của một cắt. Một số hệ quả quan trọng:

• Các cạnh nằm trong cắt nhỏ nhất đều phải đạt trạng thái đầy dòng.
• Nếu giảm dung lượng một cạnh đầy dòng mà dòng tối đa không thay đổi, thì cạnh đó không thuộc bất kỳ cắt nhỏ nhất nào.
• Mọi đường tăng đều đi qua ít nhất một cạnh thuộc cắt nhỏ nhất.
• Một cạnh đầy dòng \( (u,v) \) là cạnh thiết yếu nếu trong đồ thị dư, \( S \) có thể đến \( u \) và \( v \) có thể đến \( T \).

Tìm số cạnh nhỏ nhất trong cắt nhỏ nhất

Để tìm số lượng cạnh tối thiểu trong một cắt có dung lượng nhỏ nhất, ta có thể biến đổi mạng như sau:

1. Chạy thuật toán dòng chảy để xác định giá trị cắt nhỏ nhất.
2. Gán lại trọng số: cạnh đầy dòng nhận trọng số 1, các cạnh khác nhận trọng số lớn vô cùng (ví dụ \( \infty = m+1 \)).
3. Chạy lại thuật toán dòng chảy trên mạng mới với trọng số nhân hệ số.

Chiến lược này đảm bảo rằng kết quả cuối cùng sẽ phản ánh cả giá trị dòng lẫn số cạnh tham gia cắt. Ví dụ dưới đây sử dụng kỹ thuật mã hóa kép: nhân dung lượng gốc với \( m+1 \) rồi cộng thêm 1 để đếm số cạnh.

int main() {
    cin >> n >> m;
    source = 1, sink = n;
    head.assign(n + 1, -1);
    level.resize(n + 1);
    current.resize(n + 1);
    edges.clear();
    edges.reserve(2 * m);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w * (m + 1) + 1); // Mã hóa
    }

    long long result = dinic();
    long long minCutValue = result / (m + 1);
    long long minEdgeCount = result % (m + 1);
    cout << minCutValue << " " << minEdgeCount << endl;
    return 0;
}

Tìm tập đỉnh trong cắt nhỏ nhất

Sau khi chạy Dinic, ta có thể xác định tập đỉnh có thể đến từ nguồn trong đồ thị dư bằng DFS. Những đỉnh này thuộc phía nguồn của một cắt nhỏ nhất.

vector<bool> visited;

void dfs(int u) {
    visited[u] = true;
    for (int i = head[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        if (!visited[v] && edges[i].cap > 0) {
            dfs(v);
        }
    }
}
// Gọi dfs(source) sau khi chạy dinic()

Dòng chảy có phí tổn (Minimum Cost Maximum Flow)

Mỗi cạnh ngoài dung lượng còn có chi phí \( w(u,v) \) cho mỗi đơn vị dòng chảy. Mục tiêu là tìm dòng chảy tối đa với tổng chi phí nhỏ nhất.

Thuật toán phổ biến: kết hợp EK với SPFA để tìm đường tăng có chi phí nhỏ nhất. Mỗi lần tăng dựa trên đường đi ngắn nhất về mặt chi phí trong mạng dư.

struct WeightedEdge {
    int to, next, cap, cost;
};

vector<WeightedEdge> wedges;
vector<int> whead, dist;
vector<bool> inQueue;
vector<long long> flowIn;
vector<int> parentEdge;

bool spfa() {
    fill(dist.begin(), dist.end(), INT_MAX);
    queue<int> q;
    q.push(source);
    dist[source] = 0;
    inQueue[source] = true;
    flowIn[source] = LLONG_MAX;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;
        for (int i = whead[u]; i != -1; i = wedges[i].next) {
            int v = wedges[i].to;
            if (wedges[i].cap > 0 && dist[u] + wedges[i].cost < dist[v]) {
                dist[v] = dist[u] + wedges[i].cost;
                flowIn[v] = min(flowIn[u], (long long)wedges[i].cap);
                parentEdge[v] = i;
                if (!inQueue[v]) {
                    inQueue[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return dist[sink] != INT_MAX;
}

pair<long long, long long> minCostMaxFlow() {
    long long totalFlow = 0, totalCost = 0;
    while (spfa()) {
        long long f = flowIn[sink];
        totalFlow += f;
        totalCost += f * dist[sink];
        for (int v = sink; v != source; v = wedges[parentEdge[v]^1].to) {
            int e = parentEdge[v];
            wedges[e].cap -= f;
            wedges[e^1].cap += f;
        }
    }
    return {totalFlow, totalCost};
}