Hướng giải của Người đưa thư Trung Hoa
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Đây là bài toán Người đưa thư Trung Hoa (Chinese Postman Problem). Nếu đồ thị đã có chu trình Euler (mọi bậc đều chẵn), kết quả là tổng trọng số của tất cả các cạnh. Nếu đồ thị có \(2k\) đỉnh bậc lẻ (\(2k \le 16\)):
- Chạy thuật toán Floyd-Warshall để tìm khoảng cách ngắn nhất giữa tất cả các cặp đỉnh.
- Dùng Quy hoạch động trạng thái (Bitmask DP) để ghép đôi \(2k\) đỉnh bậc lẻ này sao cho tổng khoảng cách ghép đôi là nhỏ nhất. Tổng chi phí tối ưu sẽ bằng tổng trọng số của tất cả các cạnh cộng với tổng chi phí ghép đôi nhỏ nhất.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
for (int i = 1; i <= n; i++) dist[i][i] = 0;
long long total_sum = 0;
vector<int> deg(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
if (cin >> u >> v >> w) {
dist[u][v] = min(dist[u][v], w);
dist[v][u] = min(dist[v][u], w);
deg[u]++; deg[v]++;
total_sum += w;
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
vector<int> odds;
for (int i = 1; i <= n; i++) {
if (deg[i] % 2 != 0) {
odds.push_back(i);
}
}
if (odds.empty()) {
cout << total_sum << "\n";
return 0;
}
int k = odds.size();
vector<long long> dp(1 << k, INF);
dp[0] = 0;
for (int mask = 0; mask < (1 << k); mask++) {
if (dp[mask] == INF) continue;
int i = -1;
for (int j = 0; j < k; j++) {
if (!(mask & (1 << j))) {
i = j;
break;
}
}
if (i == -1) continue;
for (int j = i + 1; j < k; j++) {
if (!(mask & (1 << j))) {
int next_mask = mask | (1 << i) | (1 << j);
dp[next_mask] = min(dp[next_mask], dp[mask] + dist[odds[i]][odds[j]]);
}
}
}
cout << total_sum + dp[(1 << k) - 1] << "\n";
return 0;
}
Nhận xét