VOI - JOBSET
Source: VOI14 - JOBSET
Tags: Graph, Classic
Problem:
Một công ti có một danh sách N dự án chưa thực hiện được đánh số từ 1 đến N. Sau khi rà soát năng lực thực hiện của các dự án, công ti đưa ra đánh giá hiệu quả từ dự án i là p[i] (p[i] > 0 nếu đó là lợi nhuận có thể có được từ dự án, p[i] < 0 nếu đó là thua lỗ từ dự án). Việc thực hiện các dự án lại không đơn giản, có M điều kiện liên quan đến việc thực hiện các dự án. Điều kiện thứ j cho biết nếu thực hiện dự án u[j] thì phải thực hiện dự án v[j]. Hãy giúp công ti tính số tiền lãi lớn nhất có thể thu được từ việc thực hiện các dự án trong danh sách, hoặc không thực hiện dự án nào để bảo toàn vốn.
Dòng đầu là N. Dòng thứ hai là N số nguyên p[i].
Dòng thứ ba là M. M dòng sau mỗi dòng 2 số u[j], v[j].
N ≤ 500. |p[i]| < 1e6. M ≤ 1e4.
Ví dụ:
Input:
6
10 4 -5 3 -1 -2
4
2 3
2 5
6 5
4 3
Output:
11
Explanation:
Bỏ dự án 6 và thực hiện các dự án còn lại. Chú ý rằng dự án 6 nếu thực hiện thì phải thực hiện dự án 5 nhưng ngược lại thì không.
Solution:
Đây là một ứng dụng kinh điển của luồng cực đại, có tên là Project Selection Problem. Sau đây là bản dịch của mình từ lecture của giáo sư Sariel Har-Peled (phần 4) mà mình tìm được trên Math.StackExchange.
Project Selection Problem
♦ Định nghĩa: Tập hợp A ⊂ P được gọi là có thể thực hiện được nếu ∀ dự án i ∈ A, các dự án j cần thực hiện cùng với i cũng thuộc A. Nói cách khác, với mọi dự án i ∈ A và cung (i, j) ∈ E, ta có j ∈ A.
► Bổ đề 1: Không có cung nào thuộc E và thuộc (A', B').
Chứng minh: Theo định nghĩa, A có thể thực hiện được do đó với mọi cung (i, j) ∈ E và i ∈ A nên j không thể thuộc B, do đó không tồn tại cung thuộc E đồng thời thuộc (A', B').
► Bổ đề 2: Sức chứa của lát cắt (A', B'): c(A', B') = C - 𝚺(i ∈ A) p[i]
Chứng minh: Tập cạnh của H bao gồm: (i) cung thuộc E, (ii) cung từ s và (iii) cung đến t. Do A có thể thực hiện được, theo bổ đề 1, không có cung loại (i) thuộc lát cắt.
Tổng các cung loại (ii) thuộc lát cắt: X = 𝚺(i ∈ (P \ A), p[i] > 0) p[i]
Tổng các cung loại (iii) thuộc lát cắt: Y = 𝚺(j ∈ A, p[j] < 0) -p[j]
Code:
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
/// n: số dự án; m: số điều kiện; s: đỉnh phát; t: đỉnh thu
int n, m, s, t;
/// c[u][v]: sức chứa tối đa của cung (u, v)
/// f[u][v]: luồng tại cung (u, v)
int c[515][515], f[515][515];
/// change[u]: giá trị tăng của đường tăng luồng từ s đến u
/// trace[u]: truy vết đỉnh trong đường tăng luồng từ s đến u
int change[515], trace[515];
/// q: hàng đợi queue để thực hiện bfs tìm đường tăng luồng
{---------------------------------------------}
/// tìm và kiểm tra còn đường tăng luồng nào không
bool find_augment_path() {
while (!q.empty()) q.pop();
memset(trace, -1, sizeof trace);
/// bắt đầu bfs từ đỉnh phát s
q.push(s); trace[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
/// xét các đỉnh v chưa được duyệt và có thể tăng luồng
Tags: Graph, Classic
Problem:
Một công ti có một danh sách N dự án chưa thực hiện được đánh số từ 1 đến N. Sau khi rà soát năng lực thực hiện của các dự án, công ti đưa ra đánh giá hiệu quả từ dự án i là p[i] (p[i] > 0 nếu đó là lợi nhuận có thể có được từ dự án, p[i] < 0 nếu đó là thua lỗ từ dự án). Việc thực hiện các dự án lại không đơn giản, có M điều kiện liên quan đến việc thực hiện các dự án. Điều kiện thứ j cho biết nếu thực hiện dự án u[j] thì phải thực hiện dự án v[j]. Hãy giúp công ti tính số tiền lãi lớn nhất có thể thu được từ việc thực hiện các dự án trong danh sách, hoặc không thực hiện dự án nào để bảo toàn vốn.
Dòng đầu là N. Dòng thứ hai là N số nguyên p[i].
Dòng thứ ba là M. M dòng sau mỗi dòng 2 số u[j], v[j].
N ≤ 500. |p[i]| < 1e6. M ≤ 1e4.
Ví dụ:
Input:
6
10 4 -5 3 -1 -2
4
2 3
2 5
6 5
4 3
Output:
11
Explanation:
Bỏ dự án 6 và thực hiện các dự án còn lại. Chú ý rằng dự án 6 nếu thực hiện thì phải thực hiện dự án 5 nhưng ngược lại thì không.
Solution:
Đây là một ứng dụng kinh điển của luồng cực đại, có tên là Project Selection Problem. Sau đây là bản dịch của mình từ lecture của giáo sư Sariel Har-Peled (phần 4) mà mình tìm được trên Math.StackExchange.
Project Selection Problem
- P: tập hợp các dự án
- p[i]: lợi nhuận từ dự án i
(p[i] > 0: lãi; p[i] < 0: lỗ) - G = (P, E). Cung (i, j) ∈ E nếu muốn thực hiện dự án i thì phải thực hiện dự án j.
♦ Định nghĩa: Tập hợp A ⊂ P được gọi là có thể thực hiện được nếu ∀ dự án i ∈ A, các dự án j cần thực hiện cùng với i cũng thuộc A. Nói cách khác, với mọi dự án i ∈ A và cung (i, j) ∈ E, ta có j ∈ A.
- Dựng đồ thị H có tập đỉnh gồm P và 2 đỉnh s, t, tập cạnh gồm:
∀ i ∈ P, p[i] > 0, thêm cung (s, i) sức chứa p[i]
∀ j ∈ P, p[j] < 0, thêm cung (j, t) sức chứa -p[j]
∀ (u, v) ∈ E, thêm cung (u, v) và gán sức chứa +∞ - Giá trị max của luồng cực đại (lợi nhuận cao nhất có thể đạt được): C = 𝚺(i ∈ P, p[i] > 0) p[i]
- A: Tập hợp các dự án có thể thực hiện được
- A' = A ∪ {s} và B' = (P \ A) ∪ {t}
- Lát cắt s-t (A', B')
► Bổ đề 1: Không có cung nào thuộc E và thuộc (A', B').
Chứng minh: Theo định nghĩa, A có thể thực hiện được do đó với mọi cung (i, j) ∈ E và i ∈ A nên j không thể thuộc B, do đó không tồn tại cung thuộc E đồng thời thuộc (A', B').
► Bổ đề 2: Sức chứa của lát cắt (A', B'): c(A', B') = C - 𝚺(i ∈ A) p[i]
Chứng minh: Tập cạnh của H bao gồm: (i) cung thuộc E, (ii) cung từ s và (iii) cung đến t. Do A có thể thực hiện được, theo bổ đề 1, không có cung loại (i) thuộc lát cắt.
Tổng các cung loại (ii) thuộc lát cắt: X = 𝚺(i ∈ (P \ A), p[i] > 0) p[i]
Tổng các cung loại (iii) thuộc lát cắt: Y = 𝚺(j ∈ A, p[j] < 0) -p[j]
Từ định nghĩa của C, ta có:
X = 𝚺(i ∈ P, p[i] > 0) p[i] - 𝚺(i ∈ A, p[i] > 0) p[i] = C - 𝚺(i ∈ A, p[i] > 0) p[i]
X + Y = C - 𝚺(i ∈ A, p[i] > 0) p[i] + 𝚺(j ∈ A, p[j] < 0) -p[j] = C - 𝚺(i ∈ A) p[i]
► Bổ đề 3: Nếu sức chứa của lát cắt c(A', B') ≤ C, tập A = A' \ {s} có thể thực hiện được.
Chứng minh: Giả sử A không thực hiện được → tồn tại cung (i, j) sao cho i ∈ A', j ∈ B'. Mà (i, j) có sức chứa +∞ → c(A', B') > C → Giả thiết sai.
Trường hợp c(A', B') > C có 2 khả năng:
- Khả năng 1: tập A không thể thực hiện được, lúc này c(A', B') = +∞
- Khả năng 2: tập A có thể thực hiện được, theo bổ đề 2, c(A', B') = C - 𝚺(i ∈ A) p[i]
→ C - 𝚺(i ∈ A) p[i] > C → 𝚺(i ∈ A) p[i] < 0 → lỗ. Do đó ta bỏ qua trường hợp này.
Ta có lợi nhuận của một tập A có thể thực hiện được là 𝚺(i ∈ A) p[i], để 𝚺(i ∈ A) p[i] đạt max thì ta cần tìm C - 𝚺(i ∈ A) p[i] đạt min. Do đó ta đi tìm lát cắt cực tiểu của đồ thị H, nếu c(A', B') ≤ C thì A có thể thực hiện được (bổ đề 3) và ta có đáp án là C - c(A', B').
Code:
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
/// n: số dự án; m: số điều kiện; s: đỉnh phát; t: đỉnh thu
int n, m, s, t;
/// c[u][v]: sức chứa tối đa của cung (u, v)
/// f[u][v]: luồng tại cung (u, v)
int c[515][515], f[515][515];
/// change[u]: giá trị tăng của đường tăng luồng từ s đến u
/// trace[u]: truy vết đỉnh trong đường tăng luồng từ s đến u
int change[515], trace[515];
/// q: hàng đợi queue để thực hiện bfs tìm đường tăng luồng
queue <int> q;
{---------------------------------------------}
/// tìm và kiểm tra còn đường tăng luồng nào không
bool find_augment_path() {
while (!q.empty()) q.pop();
memset(trace, -1, sizeof trace);
/// bắt đầu bfs từ đỉnh phát s
q.push(s); trace[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
/// xét các đỉnh v chưa được duyệt và có thể tăng luồng
for (int v = 0; v <= n + 1; v++)
if (trace[v] == -1 && c[u][v] > f[u][v]) {
change[v] = min(change[u], c[u][v] - f[u][v]);
q.push(v); trace[v] = u;
if (v == t) return true;
}
}
return false;
}
/// tăng luồng
void increase_flow() {
int v = t;
while (v != s) {
int u = trace[v];
/// luồng xuôi u → v tăng và luồng ngược v → u giảm
/// change[t]: giá trị tăng của đường tăng luồng từ s đến t
f[u][v] += change[t];
f[v][u] -= change[t];
v = u;
}
}
/// tìm giá trị luồng cực đại
int max_flow() {
change[s] = 1e9;
int res = 0;
/// khi vẫn còn có đường tăng luồng thì tăng luồng lên và duyệt tiếp
while (find_augment_path())
res += change[t],
increase_flow();
return res;
}
int main() {
cin >> n;
int maxC = 0;
/// gán số hiệu cho đỉnh phát s và đỉnh thu t
s = 0; t = n + 1;
for (int u = 1; u <= n; u++) {
int val; cin >> val;
if (val < 0)
c[u][t] = -val;
else
c[s][u] = val,
maxC += val;
}
cin >> m;
for (int u, v; m--;)
cin >> u >> v,
c[u][v] = maxC + 1;
/// nếu c(A', B') > C thì không thực hiện dự án
cout << max(maxC - max_flow(), 0);
}
q.push(v); trace[v] = u;
if (v == t) return true;
}
}
return false;
}
/// tăng luồng
void increase_flow() {
int v = t;
while (v != s) {
int u = trace[v];
/// luồng xuôi u → v tăng và luồng ngược v → u giảm
/// change[t]: giá trị tăng của đường tăng luồng từ s đến t
f[u][v] += change[t];
f[v][u] -= change[t];
v = u;
}
}
/// tìm giá trị luồng cực đại
int max_flow() {
change[s] = 1e9;
int res = 0;
/// khi vẫn còn có đường tăng luồng thì tăng luồng lên và duyệt tiếp
while (find_augment_path())
res += change[t],
increase_flow();
return res;
}
int main() {
cin >> n;
int maxC = 0;
/// gán số hiệu cho đỉnh phát s và đỉnh thu t
s = 0; t = n + 1;
for (int u = 1; u <= n; u++) {
int val; cin >> val;
if (val < 0)
c[u][t] = -val;
else
c[s][u] = val,
maxC += val;
}
cin >> m;
for (int u, v; m--;)
cin >> u >> v,
c[u][v] = maxC + 1;
/// nếu c(A', B') > C thì không thực hiện dự án
cout << max(maxC - max_flow(), 0);
}
Nhận xét
Đăng nhận xét