Giải bài toán P1099: Hạt nhân của Mạng Cây
Bài toán này liên quan đến việc tìm hạt nhân của một mạng cây, khái niệm liên quan đến đường kính của cây và phương pháp đo trên cây (two pointers trên cây).
Phương pháp O(n^3)
Ý tưởng cơ bản là sử dụng Floyd để tính khoảng cách giữa mọi cặp đỉnh trong cây. Sau đó, ta có thể liệt kê tất cả các cặp điểm trên đường kính và với mỗi cặp, ta tính giá trị ECC (độ dài đường đi dài nhất từ một điểm đến hạt nhân) bằng công thức:
ECC = (dis[d[i]][k] + dis[d[j]][k] - dis[d[i]][d[j]]) / 2
Trong đó d[i] và d[j] là hai điểm đầu mút của hạt nhân, và k là một điểm bất kỳ trên cây.
Phương pháp O(n^2)
Ta có thể cải tiến bằng cách sử dụng tư tưởng two pointers (cây尺取). Khi điểm bắt đầu của hạt nhân được xác định, hạt nhân càng dài thì kết quả càng tối ưu. Điều này cho phép chúng ta liệt kê hạt nhân trong O(n) và với mỗi hạt nhân, ta tính giá trị ECC bằng cách xem xét khoảng cách từ các điểm trên hạt nhân đến các điểm xa nhất.
Phương pháp O(n)
Từ phương pháp O(n^2), chúng ta có thể tiếp tục tối ưu bằng cách sử dụng hàng đợi đơn điệu để xử lý khoảng cách xa nhất trong đoạn hạt nhân trong O(1). Chúng ta nhận thấy rằng chỉ có một số điểm nhất định ảnh hưởng đến kết quả cuối cùng:
- Khoảng cách từ hai đầu hạt nhân đến hai đầu đường kính
- Điểm xa nhất so với đường kính
Bằng cách xử lý riêng hai trường hợp này, chúng ta có thể giảm độ phức tạp xuống O(n).
Mã nguồn tham khảo
Giải pháp O(n^3)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 305;
int n, s;
int adj[MAXN][MAXN];
int dist[MAXN][MAXN];
int diameter[MAXN];
int diameterEnd1, diameterEnd2;
int diameterSize;
int result = 0x3f3f3f3f;
bool findDiameter(int u, int parent, int target) {
for (int v = 1; v <= n; v++) {
if (v == target && adj[u][v]) {
diameter[diameterSize++] = target;
diameter[diameterSize++] = u;
return true;
}
if (v != parent && adj[u][v]) {
if (findDiameter(v, u, target)) {
diameter[diameterSize++] = u;
return true;
}
}
}
return false;
}
void getDiameter() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] > dist[diameterEnd1][diameterEnd2]) {
diameterEnd1 = i;
diameterEnd2 = j;
}
}
}
diameterSize = 0;
findDiameter(diameterEnd1, -1, diameterEnd2);
}
int main() {
memset(dist, 0x3f, sizeof(dist));
cin >> n >> s;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u][v] = adj[v][u] = dist[u][v] = dist[v][u] = w;
}
for (int i = 1; i <= n; i++) {
dist[i][i] = 0;
}
// Floyd-Warshall
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]);
}
}
}
getDiameter();
for (int i = 0; i < diameterSize; i++) {
for (int j = i; j < diameterSize; j++) {
if (dist[diameter[i]][diameter[j]] <= s) {
int ecc = 0;
for (int k = 1; k <= n; k++) {
ecc = max(ecc, (dist[diameter[i]][k] + dist[diameter[j]][k] - dist[diameter[i]][diameter[j]]) / 2);
}
result = min(result, ecc);
}
}
}
cout << result << endl;
return 0;
}
Giải pháp O(n)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 500005;
int n, s;
int head[MAXN];
int parent[MAXN];
int isOnDiameter[MAXN];
int diameterEnd1, diameterEnd2;
int diameterSize;
long long result, finalAnswer = 1e18;
long long distanceFromRoot[MAXN], distanceFromParent[MAXN];
long long maxDistanceFromDiameter = 0;
struct Edge {
int to, next, weight;
} edges[MAXN * 2];
int edgeCount = 0;
void addEdge(int u, int v, int w) {
edges[edgeCount] = {v, head[u], w};
head[u] = edgeCount++;
edges[edgeCount] = {u, head[v], w};
head[v] = edgeCount++;
}
void dfs(int u, int parent) {
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (v == parent) continue;
parent[v] = u;
distanceFromParent[v] = edges[i].weight;
distanceFromRoot[v] = distanceFromRoot[u] + edges[i].weight;
if (distanceFromRoot[v] > distanceFromRoot[diameterEnd1]) {
diameterEnd1 = v;
}
dfs(v, u);
}
}
long long dfsFarthest(int u, int parent, long long currentDist) {
long long maxDist = currentDist;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (v != parent) {
maxDist = max(maxDist, dfsFarthest(v, u, currentDist + edges[i].weight));
}
}
return maxDist;
}
int main() {
memset(head, -1, sizeof(head));
cin >> n >> s;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
}
// Find first end of diameter
diameterEnd1 = 1;
distanceFromRoot[1] = 0;
dfs(1, -1);
// Find second end of diameter
diameterEnd2 = diameterEnd1;
memset(distanceFromRoot, 0, sizeof(distanceFromRoot));
dfs(diameterEnd1, -1);
// Build diameter array
diameterSize = 0;
for (int u = diameterEnd2; u != -1; u = parent[u]) {
diameter[diameterSize++] = u;
isOnDiameter[u] = 1;
}
// Find max distance from diameter
for (int i = 0; i < diameterSize; i++) {
int u = diameter[i];
for (int j = head[u]; j != -1; j = edges[j].next) {
int v = edges[j].to;
if (!isOnDiameter[v]) {
maxDistanceFromDiameter = max(maxDistanceFromDiameter,
dfsFarthest(v, u, edges[j].weight));
}
}
}
// Two pointers on diameter
int left = 0, right = 0;
long long currentLength = 0;
long long leftEndDist = distanceFromRoot[diameterEnd2];
long long rightEndDist = 0;
while (left < diameterSize && right < diameterSize) {
while (right < diameterSize && currentLength + distanceFromParent[diameter[right]] <= s) {
currentLength += distanceFromParent[diameter[right]];
leftEndDist -= distanceFromParent[diameter[right]];
right++;
}
finalAnswer = min(finalAnswer, max(leftEndDist, rightEndDist));
currentLength -= distanceFromParent[diameter[left]];
rightEndDist += distanceFromParent[diameter[left]];
left++;
}
cout << max(maxDistanceFromDiameter, finalAnswer) << endl;
return 0;
}