09.1 - Min-Cost Flow Cơ bản

Mạng Luồng không có chi phí âm

Giới thiệu

Tài liệu tham khảo

Trường hợp đơn giản

Bài toán

Giải quyết bài toán

Phân tích độ phức tạp

Cài đặt

Cải tiến

Nhiệm vụ 1- Cơ bản

Giới thiệu

Cho một mạng luồng G có n đỉnh, m cạnh, có một đỉnh phát s (source) và một đỉnh thu t (sink). Mỗi cạnh có một khả năng thông qua c, và một chi phí thông qua a.

Như bài trước đã thảo luận, một luồng f trên G là một cách gửi qua các cạnh một lượng nhật định sao cho lượng đó nhỏ hơn khả năng thông qua của cạnh đó, hay f(e) ≤ c(e), ∀e.

Chi phí thông qua a là chi phí tính trên mỗi đơn vị luồng. Chi phí của một luồng là tổng chi phí của luồng khi đi qua tất cả các cạnh trên đường đi từ s đến t.

Cho một số nguyên dương K, ta cần tìm một luồng có giá trị không quá K mà có chi phí nhỏ nhất. Đây là bài toán tìm luồng có chi phí nhỏ nhất (Min Cost Flow).

Nếu K là vô cực, thì bài toán trở thành Min Cost Max Flow.

Hai bài toán này coi như một, chủ đề này sẽ thảo luận về giải thuật cho bài toán cùng một số ví dụ minh họa.

Tài liệu tham khảo

CP-Algorithm - Minimum-Cost Flow
CodeForce Tutorial - Minimum Cost Flow
Topcoder - Minimum Cost Flow: Key Concept and Part two
Hackerearth - Minimum Cost Flow
Steven Halim - Competitive Programming 4 - MinCost Flow - Chapter 9, page 571 - 579

Trường hợp đơn giản

Với giả định mạng G là đơn đồ thị có hướng, không có cạnh âm.

Bài toán

Ví dụ sau đây cho một mạng G có 4 đỉnh, với đỉnh phát A, đỉnh thu D. Khả năng thông qua của tất cả các cạnh là 10, chi phí thông qua được cho như trong hình. Với K = 20, ta cần tìm luống không vượt quá K mà chi phí là thấp nhất.

Như mô tả trên chúng ta có 3 luồng đạt giá trị K = 20:

Cách 1. Gửi một luồng theo đường A -->B-->D: cost = (3+4)*10 =70.

Gửi tiếp một luống theo đường A -->D: cost = 1*10 = 10.

Tổng: cost(f) = 70 + 10 = 80.

Cách 2. Gửi một luồng theo đường A -->B-->D: cost = (3+4)*10 =70.

Gửi tiếp một luống theo đường A -->C-->D: cost = (3+5)*10 = 80.

Tổng: cost(f) = 70 + 80 = 150.

Cách 3. Gửi một luồng theo đường A -->D: cost = 1*10 =10.

Gửi tiếp một luống theo đường A-->C -->D: cost = (3+5)*10 = 80.

Tổng: cost(f) = 10 + 80 = 90.

Vậy Min Cost = 80 ( là luồng ở cách 1)

Nguồn: CP4, Steven Halim

Giải quyết bài toán

Định nghĩa mạng thặng dư Gf được định nghĩa từ G tương tự như cách định nghĩa trong thuật toán Edmonds Karp.

Giải thuật cơ bản như sau:

Nguồn: Codeforce Tutorial

Cách thực hiện ở đây khá giống tư tưởng của Edmonds Karp khi tìm luồng cực đại, chỉ khác là đường đi ngắn nhất P bây giờ không phải là số cạnh trên đường đi mà là tổng chi phí trên đường đi.

Phân tích độ phức tạp

Theo thuật toán trên, chúng ta thấy được rằng thời gian chạy của thuật toán phụ thuộc vào thời gian đạt được giới hạn K của luồng f, nếu giả định là max flow thì chính là f. Sau mỗi lần tăng luồng, ta lại tính lại đường đi ngắn nhất P, giả định thời gian này là T.

--> Độ phức tạp thời gian: O(fT)

Như vậy độ phức tạp này phụ thuộc vào các bài toán con. Ở đây có hai bài toán con, bài toán thứ nhất là cách tìm luồng cực đại và bài toán thứ 2 là tìm đường đi ngắn nhất sau mỗi lần tăng luồng.

Với bài toán tìm đường đi ngắn nhất, ta có thể dùng Ford - Bellman với độ phức tạp O(n*m), hoặc dùng Dijsktra's với O(mlogn)

Với bài toán tìm luồng cực đại, ta dùng cách như trên theo Edmons Karp với độ phức tạp O(f) hoặc dùng Dinic để giảm xuống min(f, n*C) với C là khả năng thông qua cực đại mỗi lần tìm được đường (min(c(ei) với ∈ P)

Nguồn: CP-Algorithm

Cài đặt

Cài đặt sau đây là cách cài đặt thuần chưa cải tiến, tức dùng Edmons Karp để tăng luồng và dùng Bellman-Ford để tìm đường ngắn nhất.

struct Edge

{

int from, to, capacity, cost;

};

vector<vector<int>> adj, cost, capacity;

const int INF = 1e9;

void shortest_paths(int n, int v0, vector<int>& d, vector<int>& p) {

d.assign(n, INF);

d[v0] = 0;

vector<bool> inq(n, false);

queue<int> q;

q.push(v0);

p.assign(n, -1);

while (!q.empty()) {

int u = q.front();

q.pop();

inq[u] = false;

for (int v : adj[u]) {

if (capacity[u][v] > 0 && d[v] > d[u] + cost[u][v]) {

d[v] = d[u] + cost[u][v];

p[v] = u;

if (!inq[v]) {

inq[v] = true;

q.push(v);

}

int min_cost_flow(int N, vector<Edge> edges, int K, int s, int t) {

adj.assign(N, vector<int>());

cost.assign(N, vector<int>(N, 0));

capacity.assign(N, vector<int>(N, 0));

for (Edge e : edges) {

adj[e.from].push_back(e.to);

adj[e.to].push_back(e.from);

cost[e.from][e.to] = e.cost;

cost[e.to][e.from] = -e.cost;

capacity[e.from][e.to] = e.capacity;

}

int flow = 0;

int cost = 0;

vector<int> d, p;

while (flow < K) {

shortest_paths(N, s, d, p);

if (d[t] == INF)

break;

// find max flow on that path

int f = K - flow;

int cur = t;

while (cur != s) {

f = min(f, capacity[p[cur]][cur]);

cur = p[cur];

}

// apply flow

flow += f;

cost += f * d[t];

cur = t;

while (cur != s) {

capacity[p[cur]][cur] -= f;

capacity[cur][p[cur]] += f;

cur = p[cur];

}

if (flow < K)

return -1;

else

return cost;

}

Nguồn: CP-Algorithm

Thêm hàm main để hoàn thiện code trên và thực thi với các testcase mẫu sau đây:

Test 1:

Input: S = 0, T = 4, cap[ ][ ] = {{0, 3, 4, 5, 0}, {0, 0, 2, 0, 0}, {0, 0, 0, 4, 1}, {0, 0, 0, 0, 10}, {0, 0, 0, 0, 0}},
cost[ ][ ] = {{0, 1, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}}
Output: 10 1
Explanation:
For given graph, Max flow = 10 and Min cost = 1.

Test 2:

Input: S = 0, T = 4, cost[][] = { { 0, 1, 0, 0, 2 }, { 0, 0, 0, 3, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0 } }
cap[][] = { { 0, 3, 1, 0, 3 }, { 0, 0, 2, 0, 0 }, { 0, 0, 0, 1, 6 }, { 0, 0, 0, 0, 2 }, { 0, 0, 0, 0, 0 } }
Output: 6 8

Cải tiến

Giải thuật cải tiến được đề xuất như sau:

Using DinitZ's có nghĩa là chúng ta thực hiện đẩy thử nhiều luồng nếu còn được, cụ thể như sau:

Nhiệm vụ 1- Cơ bản

Nhiệm vụ 1.0 - Cài đặt lại ví dụ trên với việc cải tiến bằng Dinic

Nhiệm vụ 1.1- UVa - 10594 - Data Flow

Nhiệm vụ 1.2- CSES - Task Assignment

Nhiệm vụ 1.3 - Thực hiện contest ngắn - Min Cost Flow 1