Mô Hình Luồng Mạng Cơ Bản
Mạng luồng có thể được hình dung như một đồ thị có hướng, trong đó mỗi cạnh sở hữu một giới hạn về khả năng vận chuyển. Tồn tại một đỉnh nguồn phát ra luồng và một đỉnh đích thu nhận luồng. Ký hiệu f(u, v) là luồng thực tế từ u đến v, và c(u, v) là khả năng thông qua tối đa của cạnh đó. Đỉnh nguồn ký hiệu là S, đỉnh đích là T.
Một luồng hợp lệ cần thỏa mãn các điều kiện sau:
- Tính phản đối xứng:
f(u, v) = -f(v, u). Luồng âm biểu thị chiều ngược lại. - Ràng buộc khả năng thông qua:
f(u, v) ≤ c(u, v). - Bảo toàn luồng: Tại mọi đỉnh trung gian (khác
SvàT), tổng luồng vào bằng tổng luồng ra.
Mục tiêu của bài toán luồng cực đại là tìm cách phân phối luồng sao cho tổng lượng thoát khỏi S (hoặc vào T) là lớn nhất.
Mạng Tàn Dư Và Đường Tăng Luồng
Khái niệm mạng tàn dư (residual network) đóng vai trò then chốt. Với mỗi cạnh, lượng khả năng thông qua còn lại được tính bằng r(u, v) = c(u, v) - f(u, v). Định lý điều chỉnh mạng tàn dư chỉ ra rằng mọi luồng hợp lệ trên mạng gốc đều có thể đạt được bằng cách điều chỉnh luồng trên mạng tàn dư.
Thuật toán tìm luồng cực đại dựa trên việc liên tục tìm các đường tăng luồng (augmenting paths) – các đường đi từ S đến T trên mạng tàn dư mà mọi cạnh đều có dung lượng dương. Quá trình tăng luồng dọc theo đường này cho đến khi không còn đường tăng nào nữa sẽ đảm bảo đạt được luồng cực đại.
Thuật Toán Dinic
Thuật toán Dinic cải tiến hiệu suất bằng cách xây dựng đồ thị phân tầng (level graph) thông qua BFS, chỉ xét các cạnh thỏa mãn level[v] = level[u] + 1. Sau đó, nó thực hiện nhiều đường tăng luồng cùng lúc bằng DFS. Kỹ thuật tối ưu hóa cung hiện tại (current arc optimization) giúp giảm độ phức tạp xuống O(V²E) trong trường hợp tổng quát.
Dưới đây là cài đặt mẫu cho thuật toán Dinic sử dụng danh sách kề dạng chuỗi tiến (chain forward star):
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const long long INF_FLOW = 1e18;
struct Edge {
int to, next_edge;
long long capacity;
};
int head[MAXN], edge_count = 0;
Edge edges[MAXN * 2];
int level[MAXN], ptr[MAXN];
int source, sink;
void init_graph() {
memset(head, -1, sizeof(head));
edge_count = 0;
}
void add_directed_edge(int u, int v, long long cap) {
edges[edge_count] = {v, head[u], cap};
head[u] = edge_count++;
edges[edge_count] = {u, head[v], 0}; // Reverse edge
head[v] = edge_count++;
}
bool build_level_graph() {
memset(level, -1, sizeof(level));
level[source] = 0;
queue<int> q;
q.push(source);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i != -1; i = edges[i].next_edge) {
int v = edges[i].to;
if (edges[i].capacity > 0 && level[v] == -1) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[sink] != -1;
}
long long push_flow(int u, long long pushed) {
if (pushed == 0 || u == sink) return pushed;
for (int &i = ptr[u]; i != -1; i = edges[i].next_edge) {
int v = edges[i].to;
if (level[v] != level[u] + 1 || edges[i].capacity == 0) continue;
long long tr = push_flow(v, min(pushed, edges[i].capacity));
if (tr == 0) continue;
edges[i].capacity -= tr;
edges[i ^ 1].capacity += tr;
return tr;
}
return 0;
}
long long dinic_max_flow() {
long long total_flow = 0;
while (build_level_graph()) {
memcpy(ptr, head, sizeof(head));
while (long long pushed = push_flow(source, INF_FLOW)) {
total_flow += pushed;
}
}
return total_flow;
}
Ứng Dụng Luồng Cực Đại
Các bài toán thực tế thường yêu cầu xây dựng mô hình đồ thị phù hợp trước khi áp dụng thuật toán.
Bài Toán Cầu Nguy Hiểm
Vấn đề yêu cầu kiểm tra tính khả thi của việc di chuyển giữa các điểm với ràng buộc về số lần qua cầu. Mô hình hóa bằng cách đặt khả năng thông qua của cầu nguy hiểm là 2, cầu thường là vô cực. Điểm đặc biệt là cần kiểm tra tính đối xứng: chạy luồng cực đại hai lần, lần thứ hai hoán đổi vị trí đích của hai cặp điểm. Nếu cả hai lần đều đạt lưu lượng yêu cầu, bài toán có nghiệm.
Bài Toán Ghép Sách
Đây là bài toán ghép cặp có ràng buộc. Mỗi quyển sách cần được ghép với một quyển bài tập và một quyển đáp án. Kỹ thuật tách đỉnh (node splitting) được áp dụng cho节点 sách: tạo hai đỉnh đại diện cho sách, nối chúng bằng một cạnh có khả năng thông qua bằng 1. Điều này đảm bảo mỗi quyển sách chỉ được sử dụng đúng một lần trong toàn bộ hệ thống ghép nối.
Bài Toán Di Chuyển Liên Hành Tinh
Khi yếu tố thời gian tham gia vào mô hình, ta sử dụng đồ thị mở rộng theo thời gian. Mỗi trạm vũ trụ tại mỗi thời điểm t là một đỉnh riêng biệt. Các cạnh nối thể hiện việc chờ đợi tại trạm hoặc di chuyển bằng tàu vũ trụ giữa các thời điểm. Thuật toán chạy tăng dần thời gian cho đến khi luồng đạt đủ số người cần di chuyển.
Luồng Chi Phí Cực Tiểu
Mô hình này mở rộng bài toán luồng cực đại bằng cách gán thêm chi phí cho mỗi đơn vị luồng trên cạnh. Mục tiêu là tìm luồng cực đại sao cho tổng chi phí là nhỏ nhất. Điều kiện cần và đủ để đạt chi phí tối ưu là mạng tàn dư không tồn tại chu trình âm.
Thuật toán phổ biến là SSP (Successive Shortest Path), sử dụng SPFA hoặc Dijkstra (với thế vị) để tìm đường đi ngắn nhất về chi phí trên mạng tàn dư rồi tăng luồng.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const long long INF_COST = 1e15;
struct Edge {
int to, next_edge;
int capacity;
int cost;
};
int head[MAXN], edge_count = 0;
Edge edges[MAXN * 4];
long long dist[MAXN];
int parent_edge[MAXN];
bool in_queue[MAXN];
int source, sink;
void add_edge_with_cost(int u, int v, int cap, int cost) {
edges[edge_count] = {v, head[u], cap, cost};
head[u] = edge_count++;
edges[edge_count] = {u, head[v], 0, -cost};
head[v] = edge_count++;
}
bool spfa() {
fill(dist, dist + MAXN, INF_COST);
memset(in_queue, 0, sizeof(in_queue));
memset(parent_edge, -1, sizeof(parent_edge));
queue<int> q;
q.push(source);
dist[source] = 0;
in_queue[source] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
in_queue[u] = false;
for (int i = head[u]; i != -1; i = edges[i].next_edge) {
int v = edges[i].to;
if (edges[i].capacity > 0 && dist[v] > dist[u] + edges[i].cost) {
dist[v] = dist[u] + edges[i].cost;
parent_edge[v] = i;
if (!in_queue[v]) {
q.push(v);
in_queue[v] = true;
}
}
}
}
return dist[sink] != INF_COST;
}
long long min_cost_max_flow() {
long long total_cost = 0;
while (spfa()) {
int flow = INT_MAX;
int curr = sink;
while (curr != source) {
int id = parent_edge[curr];
flow = min(flow, edges[id].capacity);
curr = edges[id ^ 1].to;
}
total_cost += (long long)flow * dist[sink];
curr = sink;
while (curr != source) {
int id = parent_edge[curr];
edges[id].capacity -= flow;
edges[id ^ 1].capacity += flow;
curr = edges[id ^ 1].to;
}
}
return total_cost;
}
Ứng Dụng Luồng Chi Phí
Bài toán lấy số trong lưới ô vuông yêu cầu chọn các đường đi sao cho tổng số thu được là lớn nhất với k lần đi. Mô hình hóa bằng cách tách mỗi ô thành hai đỉnh (vào và ra). Cạnh nối giữa chúng có khả năng thông qua 1 với chi phí bằng giá trị ô (lấy một lần), và khả năng thông qua k-1 với chi phí 0 (đi qua nhưng không lấy số).
Bài toán phân công công việc là dạng điển hình của ghép cặp có trọng số. Tạo nguồn nối tới người làm, công việc nối tới đích, cạnh giữa người và việc mang chi phí hiệu suất. Chạy luồng chi phí cực tiểu và cực đại tương ứng để tìm phương án tối ưu.
Cắt Cực Tiểu Và Định Lý Luồng
Một phép cắt chia tập đỉnh thành hai phần rời nhau chứa nguồn và đích. Capacidad của cắt là tổng khả năng thông qua các cạnh đi từ phần chứa nguồn sang phần chứa đích. Định lý Luồng cực đại - Cắt cực tiểu khẳng định giá trị luồng cực đại luôn bằng khả năng thông qua của cắt cực tiểu.
Ứng dụng quan trọng nhất của định lý này là giải quyết các bài toán đóng kín hoặc loại bỏ phần tử với chi phí nhỏ nhất. Bằng cách xây dựng đồ thị sao cho cắt cực tiểu tương ứng với chi phí cần loại bỏ, ta quy bài toán về tìm luồng cực đại.
Ghép Cặp Trên Đồ Thị Hai Phía
Đồ thị hai phía là đồ thị mà tập đỉnh có thể chia thành hai tập độc lập. Bài toán tìm ghép cặp cực đại (nhiều cạnh nhất không chung đỉnh) có thể quy về bài toán luồng cực đại. Thêm nguồn nối tới tập đỉnh bên trái, tập đỉnh bên phải nối tới đích, tất cả khả năng thông qua bằng 1. Các cạnh gốc của đồ thị hai phía cũng có khả năng thông qua 1 (hoặc vô cực).
Bài Toán Hiệp Sĩ
Trên bàn cờ, các ô có thể chia thành hai tập dựa trên tổng tọa độ chẵn lẻ. Các quân hiệp sĩ chỉ tấn công ô khác màu. Để tìm số lượng hiệp sĩ tối đa đặt được sao cho không ăn nhau, ta xây dựng đồ thị hai phía. Cắt cực tiểu trên đồ thị này tương ứng với số ô ít nhất cần bỏ đi để loại bỏ mọi xung đột. Kết quả là tổng số ô hợp lệ trừ đi giá trị luồng cực đại.
Bài Toán Lấy Số Trên Lưới
Tương tự bài toán hiệp sĩ, việc chọn các ô kề nhau bị cấm có thể mô hình hóa bằng cắt cực tiểu. Nối nguồn tới ô màu trắng, ô màu đen nối tới đích với khả năng thông qua bằng giá trị ô. Các cạnh kề nhau có khả năng thông qua vô cực. Luồng cực đại tìm được chính là tổng giá trị nhỏ nhất của các ô cần loại bỏ để thỏa mãn điều kiện không chọn hai ô kề nhau.