Hướng dẫn giải của [2526 VTT THPT KS1] Bài 4: Đường đi dài nhất
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
Đồ thị ban đầu là rừng (không có chu trình). Ta chỉ được thêm cạnh sao cho vẫn là rừng, tức là chỉ nối được các cây khác nhau. Vì vậy cách tốt nhất là nối các cây đầu-cuối thành một đường dài, trong mỗi cây dùng đường kính (đường đi dài nhất). Đáp án là tổng số đỉnh trên đường kính của tất cả các cây (đỉnh cô lập tính 1). Kiểm tra ví dụ 2: hai cây hình sao, mỗi cây đường kính 3 đỉnh, tổng 6.
Sub 1: BFS từ mọi đỉnh — ~O(n^2)~, dùng khi ~n \le 3000~
Gom từng cây, chạy BFS từ mỗi đỉnh để tìm khoảng cách lớn nhất, lấy đó làm đường kính. Nếu chỉ nộp sub này: đúng 15/39 test.
Sub 2: Hai lần BFS — ~O(n + m)~
Trong mỗi cây, BFS từ một đỉnh bất kỳ để tìm đỉnh xa nhất ~a~ (một đầu của đường kính), rồi BFS từ ~a~; khoảng cách lớn nhất cộng 1 là số đỉnh của đường kính. Cộng dồn theo các cây (dùng ~long long~ cho an toàn). Nếu chỉ nộp sub này: đúng 39/39 test.
Chương trình hoàn chỉnh
Hàm main đọc đồ thị; ~n \le 3000~ gọi sub1 (15 test), lớn hơn gọi sub2 (24 test). 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;
int n, m;
vector<int> g[100005];
int distv[100005], comp[100005];
// BFS từ s, trả về đỉnh xa nhất; distv[] là khoảng cách (số cạnh), chỉ trong thành phần của s
int bfs(int s) {
vector<int> q = {s};
distv[s] = 0;
int last = s;
for (size_t h = 0; h < q.size(); h++) {
int u = q[h];
last = u;
for (int v : g[u])
if (distv[v] < 0) { distv[v] = distv[u] + 1; q.push_back(v); }
}
return last;
}
// Đồ thị là rừng (không chu trình). Ta nối các thành phần đầu-cuối bằng các cạnh mới thì vẫn là rừng,
// nên đáp án = tổng số đỉnh trên đường kính của mỗi cây.
// Sub 1: với mỗi cây, thử BFS từ mọi đỉnh — O(n^2), dùng khi n <= 3000
void sub1() {
memset(comp, -1, sizeof comp);
long long ans = 0;
for (int s = 1; s <= n; s++) {
if (comp[s] >= 0) continue;
// gom thành phần
vector<int> nodes = {s};
comp[s] = s;
for (size_t h = 0; h < nodes.size(); h++)
for (int v : g[nodes[h]])
if (comp[v] < 0) { comp[v] = s; nodes.push_back(v); }
int diam = 0;
for (int u : nodes) {
for (int v : nodes) distv[v] = -1;
bfs(u);
for (int v : nodes) diam = max(diam, distv[v]);
}
ans += diam + 1; // số đỉnh = số cạnh + 1
}
cout << ans << "\n";
}
// Sub 2: đường kính bằng hai lần BFS — O(n)
void sub2() {
vector<char> done(n + 1, 0);
for (int i = 1; i <= n; i++) distv[i] = -1;
long long ans = 0;
for (int s = 1; s <= n; s++) {
if (done[s]) continue;
int a = bfs(s); // đỉnh xa nhất từ s là một đầu của đường kính
// gom thành phần để đặt lại khoảng cách
vector<int> nodes = {s};
done[s] = 1;
for (size_t h = 0; h < nodes.size(); h++)
for (int v : g[nodes[h]])
if (!done[v]) { done[v] = 1; nodes.push_back(v); }
for (int v : nodes) distv[v] = -1;
int b = bfs(a); // BFS từ đầu a, đỉnh xa nhất cho độ dài đường kính
ans += distv[b] + 1;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
g[a].push_back(b); g[b].push_back(a);
}
if (n <= 3000) sub1();
else sub2();
return 0;
}
Bình luận