Hướng dẫn giải của [KS cụm 2 QL] Câu 4: Đường đi
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Theo ví dụ (đáp án 85 = 50 + 20 + 15 trên chu trình 2 - 3 - 5), yêu cầu thực chất là tìm chu trình đơn có ít nhất 3 đỉnh với tổng chi phí nhỏ nhất, in tổng chi phí và số đỉnh của chu trình; không có chu trình thì in 0. (Đường 4 - 1 - 2 chỉ tốn 17 nhưng không phải đáp án, và ví dụ 2 là cây nên in 0 — vậy "đường đi" ở đây phải quay về điểm xuất phát.) Lưu ý: nếu có nhiều chu trình cùng chi phí nhỏ nhất, chương trình in số đỉnh ít nhất (dữ liệu chấm không có trường hợp này). Giữa hai đỉnh chỉ cần giữ cạnh nhẹ nhất vì chu trình từ 3 đỉnh không dùng hai cạnh song song.
Sub 1: Vét cạn bằng DFS — dùng khi ~N \le 10~
Với mỗi đỉnh xuất phát ~st~ (là đỉnh nhỏ nhất của chu trình), DFS qua các đỉnh lớn hơn chưa thăm, khi quay lại ~st~ với ít nhất 3 đỉnh thì cập nhật đáp án. Nếu chỉ nộp sub này: đúng 5/20 test.
Sub 2: Floyd tìm chu trình ngắn nhất — ~O(N^3)~
Xử lý đỉnh ~k~ theo thứ tự tăng dần. Trước khi dùng ~k~ làm đỉnh trung gian, ma trận ~d[i][j]~ là đường ngắn nhất giữa ~i~ và ~j~ chỉ qua các đỉnh nhỏ hơn ~k~. Chu trình có đỉnh lớn nhất là ~k~ gồm đường ~i \to j~ cộng hai cạnh ~j-k~ và ~k-i~ (~i \ne j~), vì thế không bị lặp đỉnh. Ta lưu thêm số đỉnh của đường đi ngắn nhất để in ~K~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc đồ thị (bỏ khuyên, lấy cạnh nhẹ nhất giữa hai đỉnh); ~N \le 10~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
int n, m;
long long w[105][105]; // w[u][v] = cạnh nhỏ nhất giữa u và v (INF nếu không có)
// Sub 1: vét cạn - duyệt mọi chu trình đơn bằng DFS, dùng khi N <= 10
long long bestC; int bestK;
int st;
bool vis[105];
void dfs(int u, int len, long long cost) {
for (int v = 1; v <= n; v++) {
if (w[u][v] >= INF) continue;
if (v == st && len >= 3) {
long long c = cost + w[u][v];
if (c < bestC || (c == bestC && len < bestK)) { bestC = c; bestK = len; }
} else if (v > st && !vis[v]) { // st là đỉnh nhỏ nhất của chu trình
vis[v] = true;
dfs(v, len + 1, cost + w[u][v]);
vis[v] = false;
}
}
}
void sub1() {
bestC = INF; bestK = 0;
for (st = 1; st <= n; st++) {
memset(vis, 0, sizeof vis);
vis[st] = true;
dfs(st, 1, 0);
}
if (bestC >= INF) puts("0");
else printf("1\n%lld\n%d\n", bestC, bestK);
}
// Sub 2: Floyd tìm chu trình ngắn nhất, O(N^3), dùng khi N <= 100
void sub2() {
static long long d[105][105];
static int cnt[105][105]; // số đỉnh trên đường đi ngắn nhất d[i][j] (tính cả hai đầu)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) { d[i][j] = (i == j ? 0 : w[i][j]); cnt[i][j] = (i == j ? 1 : 2); }
bestC = INF; bestK = 0;
for (int k = 1; k <= n; k++) {
// chu trình có đỉnh lớn nhất là k: i - ... - j (trung gian < k), j - k, k - i
for (int i = 1; i < k; i++)
for (int j = i + 1; j < k; j++)
if (w[j][k] < INF && w[k][i] < INF && d[i][j] < INF) {
long long c = d[i][j] + w[j][k] + w[k][i];
int kk = cnt[i][j] + 1;
if (c < bestC || (c == bestC && kk < bestK)) { bestC = c; bestK = kk; }
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][k] + d[k][j] < d[i][j] ||
(d[i][k] + d[k][j] == d[i][j] && d[i][j] < INF && cnt[i][k] + cnt[k][j] - 1 < cnt[i][j])) {
d[i][j] = d[i][k] + d[k][j];
cnt[i][j] = cnt[i][k] + cnt[k][j] - 1;
}
}
if (bestC >= INF) puts("0");
else printf("1\n%lld\n%d\n", bestC, bestK);
}
int main() {
freopen("CAU4.inp", "r", stdin);
freopen("CAU4.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) w[i][j] = INF;
for (int i = 0; i < m; i++) {
int u, v; long long c;
scanf("%d %d %lld", &u, &v, &c);
if (u != v) w[u][v] = w[v][u] = min(w[u][v], c);
}
if (n <= 10) sub1();
else sub2();
return 0;
}
Bình luận