Chi Phí Ít Nhất Để Kết Nối Hai Nhóm Điểm
Đề bài
Bạn được cho hai nhóm điểm: nhóm thứ nhất có size1 điểm, nhóm thứ hai có size2 điểm, và size1 ≥ size2.
Chi phí kết nối giữa hai điểm bất kỳ được cho trong một ma trận size1 × size2, trong đó cost[i][j] là chi phí để kết nối điểm $i$ của nhóm thứ nhất với điểm $j$ của nhóm thứ hai.
Hai nhóm được coi là kết nối nếu mỗi điểm trong cả hai nhóm đều được kết nối với một hoặc nhiều điểm ở nhóm đối diện. Nói cách khác:
- Mỗi điểm ở nhóm thứ nhất phải được kết nối với ít nhất một điểm ở nhóm thứ hai.
- Mỗi điểm ở nhóm thứ hai phải được kết nối với ít nhất một điểm ở nhóm thứ nhất.
Yêu cầu: hãy tìm chi phí tối thiểu để kết nối hai nhóm điểm.
Input
- Dòng đầu tiên chứa hai số nguyên
size1vàsize2($1 \le$ size2 $\le$ size1 $\le 12$) — kích thước của hai nhóm. size1dòng tiếp theo, mỗi dòng chứasize2số nguyêncost[i][j]($0 \le$ cost[i][j] $\le 100$) — ma trận chi phí kết nối.
Output: một số nguyên duy nhất là chi phí tối thiểu tìm được.
Subtask
- 20% số test đầu tiên có $1 \le$ size2 $\le$ size1 $\le 5$.
- 80% số test còn lại không có giới hạn gì thêm.
| Input | Output | Giải thích |
|---|---|---|
2 2 15 96 36 2 | 17 | Cách kết nối tối ưu: điểm 1 (nhóm 1) nối với điểm A (nhóm 2) – chi phí 15; điểm 2 (nhóm 1) nối với điểm B (nhóm 2) – chi phí 2. Tổng chi phí = 15 + 2 = 17. |
3 3 1 3 5 4 1 1 1 5 3 | 4 | Cách kết nối tối ưu: 1–A (1), 2–B (1), 2–C (1), 3–A (1). Tổng = 1 + 1 + 1 + 1 = 4. Lưu ý: một điểm có thể kết nối với nhiều điểm ở nhóm kia. |
5 3 2 5 1 3 4 7 8 1 2 6 2 4 3 8 8 | 10 |
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm lời giải để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesTóm tắt đề bài: bạn được cho size1 điểm thuộc nhóm 1, size2 điểm thuộc nhóm 2. Chi phí để nối điểm $i$ của nhóm 1 với điểm $j$ của nhóm 2 là cost[i][j]. Hãy nối các điểm sao cho mọi điểm của nhóm 1 đều được nối với ít nhất 1 điểm nhóm 2, mọi điểm của nhóm 2 đều được nối với ít nhất 1 điểm nhóm 1, và tổng chi phí ít nhất có thể.
100%Quy hoạch động + bitmask
Để biết những điểm nào của nhóm 2 đã được nối, ta có thể dựa vào tập hợp, và để biểu diễn tập hợp ta dùng dãy bit (bitmask): bit thứ $j$ bằng 1 nghĩa là điểm $j$ của nhóm 2 đã được nối. Vì size2 $\le 12$ nên chỉ có tối đa $2^{12} = 4096$ tập.
Gọi dp[i][mask] là chi phí nhỏ nhất khi ta đã xét xong $i$ điểm đầu tiên của nhóm 1 (mỗi điểm đều đã được nối ít nhất 1 lần), và tập các điểm của nhóm 2 đã được nối là mask. Khởi tạo tất cả dp[i][mask] bằng dương vô cực, ngoại trừ dp[0][0] = 0.
Với dp[i][mask] khác dương vô cực, nếu ta quyết định nối điểm tiếp theo (điểm $i$ của nhóm 1, đánh số từ 0) với một tập các điểm nextmask của nhóm 2, thì chi phí cộng thêm là sumCost[i][nextmask] – tổng chi phí nối điểm $i$ với tất cả các điểm trong nextmask. Ta chuyển trạng thái:
Tuy nhiên, nếu làm như này sẽ bị time out vì phải duyệt $i$, duyệt mask và duyệt nextmask: $12 \cdot 4096 \cdot 4096 \approx 2 \cdot 10^8$ phép tính. Ta có nhận xét sau:
nextmask là tập con của mask (nối vào những điểm đã được nối rồi), hoặc là tập không giao với mask (chỉ nối vào những điểm chưa được nối). Vì vậy với mỗi mask, ta chỉ duyệt những nextmask như vậy, độ phức tạp giảm xuống rất nhiều.Ví dụ với size2 = 3 (các điểm A, B, C) và mask hiện tại là {A, C}:
| mask hiện tại | nextmask là tập con của mask | nextmask không giao với mask | Bị bỏ qua |
|---|---|---|---|
| 101 = {A, C} | {A}, {C}, {A, C} | {B} | {A, B}, {B, C}, {A, B, C} |
Vì sao bỏ qua các nextmask "lai" vẫn đúng? (mình giải thích thêm)
Một nextmask "lai" là tập vừa chứa điểm đã nối, vừa chứa điểm chưa nối. Phần "đã nối" trong đó không giúp phủ thêm điểm nào mới của nhóm 2 mà chỉ tốn thêm chi phí (chi phí $\ge 0$), nên bỏ phần đó đi thì vẫn được kết quả không tệ hơn: chỉ giữ lại phần "chưa nối" (là tập không giao với mask). Phần "đã nối" chỉ cần thiết khi điểm đang xét không có điểm chưa nối nào để nối, mà khi đó nó là tập con của mask – trường hợp này vẫn được xét. Thực ra chỉ cần tập con gồm đúng 1 điểm là đủ, nhưng xét hết các tập con cũng không làm sai.
Em nhập ma trận chi phí (mỗi hàng là 1 điểm của nhóm 1, các hàng cách nhau bởi dấu ;) rồi bấm Tiếp để xem từng bước: mỗi bước lấy 1 trạng thái dp[i][mask] đã đạt được, thử nối điểm thứ $i + 1$ với các nextmask hợp lệ (tập con của mask hoặc không giao với mask) và cập nhật hàng tiếp theo. Cột của bảng ghi tập điểm nhóm 2 đã được nối:
Đáp án là dp[size1][(1 << size2) - 1]: đã xét hết các điểm nhóm 1 và mọi điểm nhóm 2 đều đã được nối.
Đánh giá độ phức tạp: với mỗi mask, số tập con của mask cộng số tập con của phần bù là $2^{|mask|} + 2^{m - |mask|}$; cộng trên mọi mask thì khoảng $2 \cdot 3^{m}$, nhân với số điểm nhóm 1 ra $O(3^{\text{size2}} \cdot \text{size1})$. Với size1 = size2 = 12 là khoảng 12 triệu phép tính.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000005;
int dp[13][(1 << 12) + 5];
int sumCost[13][(1 << 12) + 5];
vector<int> listMask[(1 << 12) + 5];
int connectTwoGroups(vector<vector<int>> &cost){
int n = (int)cost.size();
int m = (int)cost[0].size();
// Khởi tạo mảng dp và sumCost
for(int i = 0; i <= n; i++){
for(int mask = 0; mask < (1 << m); mask++){
dp[i][mask] = inf;
sumCost[i][mask] = 0;
}
}
// Tính tổng chi phí cho mỗi điểm i với mỗi mask
for(int i = 0; i < n; i++){
for(int mask = 0; mask < (1 << m); mask++){
for(int j = 0; j < m; j++){
if((mask & (1 << j)) > 0){
sumCost[i][mask] += cost[i][j];
}
}
}
}
// Xây dựng danh sách các mask có thể chọn từ mask hiện tại
for(int mask = 0; mask < (1 << m); mask++){
listMask[mask].clear();
for(int nextmask = 1; nextmask < (1 << m); nextmask++){
if((mask & nextmask) == 0){
listMask[mask].push_back(nextmask);
continue;
}
if((mask & nextmask) == nextmask){
listMask[mask].push_back(nextmask);
continue;
}
}
}
// Quy hoạch động
dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int mask = 0; mask < (1 << m); mask++){
if(dp[i][mask] == inf){
continue;
}
for(int j = 0; j < (int)listMask[mask].size(); j++){
int nextmask = listMask[mask][j];
dp[i + 1][mask | nextmask] = min(dp[i + 1][mask | nextmask],
dp[i][mask] + sumCost[i][nextmask]);
}
}
}
return dp[n][(1 << m) - 1];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int size1, size2;
cin >> size1 >> size2;
vector<vector<int>> cost(size1, vector<int>(size2));
for(int i = 0; i < size1; i++){
for(int j = 0; j < size2; j++){
cin >> cost[i][j];
}
}
int result = connectTwoGroups(cost);
cout << result << endl;
return 0;
}import sys
def connectTwoGroups(cost):
n = len(cost)
m = len(cost[0])
full = 1 << m
inf = 10 ** 9
# sumCost[i][mask]: tổng chi phí nối điểm i (nhóm 1) với các điểm trong mask (nhóm 2)
sumCost = []
for i in range(n):
row = [0] * full
for mask in range(1, full):
low = mask & -mask
row[mask] = row[mask ^ low] + cost[i][low.bit_length() - 1]
sumCost.append(row)
# listMask[mask]: các nextmask là tập con của mask hoặc không giao với mask
listMask = []
for mask in range(full):
lst = []
sub = mask # các tập con khác rỗng của mask
while sub:
lst.append(sub)
sub = (sub - 1) & mask
rest = (full - 1) ^ mask # các tập con khác rỗng của phần bù
sub = rest
while sub:
lst.append(sub)
sub = (sub - 1) & rest
listMask.append(lst)
dp = [inf] * full
dp[0] = 0
for i in range(n):
ndp = [inf] * full
sc = sumCost[i]
for mask in range(full):
cur = dp[mask]
if cur == inf:
continue
for nextmask in listMask[mask]:
val = cur + sc[nextmask]
if val < ndp[mask | nextmask]:
ndp[mask | nextmask] = val
dp = ndp
return dp[full - 1]
data = sys.stdin.read().split()
size1, size2 = int(data[0]), int(data[1])
cost = [[int(data[2 + i * size2 + j]) for j in range(size2)] for i in range(size1)]
print(connectTwoGroups(cost))Trong code, sumCost[i][mask] được tính sẵn bằng cách duyệt mọi bit của mask; listMask[mask] lưu sẵn danh sách các nextmask hợp lệ của từng mask. Bản Python mình viết thêm dùng mẹo duyệt tập con sub = (sub - 1) & mask để liệt kê nhanh các tập con thay vì thử cả 4096 tập, và chỉ giữ 2 tầng dp để tiết kiệm bộ nhớ.
Mình đã kiểm tra bản C++ và Python với 600 ma trận ngẫu nhiên (so với cách thử mọi tập cạnh khi ma trận nhỏ và với một cách quy hoạch động khác khi ma trận lớn hơn), đều cho cùng kết quả. Với ma trận $12 \times 12$, bản C++ chạy khoảng 0.05 giây, bản Python khoảng 0.9 giây.
Nhận xét
Đăng nhận xét