Cây Kruskal tái cấu trúc (Kruskal Reconstruction Tree)
Quy trình xây dựng cây Kruskal tái cấu trúc:
- Mỗi đỉnh trong đồ thị gốc là một nút lá của cây Kruskal tái cấu trúc, ban đầu chúng không liên thông với nhau.
- Xét các cạnh có trọng số nhỏ trước, sau đó đến các cạnh có trọng số lớn. Nếu cạnh giúp tăng tính liên thông thì được chọn, nếu không thì bỏ qua.
- Khi một cạnh được chọn, cạnh đó trở thành một nút không phải lá (nút trong) của cây Kruskal tái cấu trúc, đóng vai trò là nút cha, kết nối hai thành phần liên thông.
- Quá trình kết thúc sau khi xét hết tất cả các cạnh. Đồ thị gốc có bao nhiêu vùng liên thông thì sẽ có bấy nhiêu cây Kruskal tái cấu trúc.
- Mỗi cây Kruskal tái cấu trúc cần được duyệt DFS để xây dựng bảng nhân (sparse table) nhằm thu thập và duy trì thông tin.
Nguyên lý của cây Kruskal tái cấu trúc
Các cạnh có trọng số nhỏ được xét trước, các cạnh có trọng số lớn được xét sau. Điều này đảm bảo cây khung nhỏ nhất (Minimum Spanning Tree) được xây dựng đồng thời cũng là cây 'bottleneck' nhỏ nhất (Minimum Bottleneck Tree).
Trong cây Kruskal tái cấu trúc, nút càng lên cao (càng gần gốc) thì trọng số cạnh đại diện càng lớn, và do đó, tính liên thông mà nó mang lại cũng càng lớn.
Đối với bất kỳ cặp đỉnh (x, y) nào, việc tìm tổ tiên chung gần nhất (LCA) của x và y trên cây Kruskal tái cấu trúc cho ta biết 'bottleneck' trọng số nhỏ nhất để kết nối x và y (tức là giá trị lớn nhất nhỏ nhất trong tất cả các cây khung: min(max edge weight)).
Ví dụ 1: Điều hướng giữa các vì sao
struct canh // Định nghĩa toàn cục để lớp SparseTable có thể đọc đồ thị của cây tái cấu trúc
{
int to, next;
};
struct BangNhan // Xây dựng bảng nhân (Sparse Table) cho cây Kruskal tái cấu trúc để tìm LCA
{
vector<int> depth;
vector<vector<int>> st; // Sparse Table: st[i][s] là nút mà i nhảy lên 2^s bước
vector<int> head; // Con trỏ đầu của danh sách kề (chain forward star)
int cnt; // Bộ đếm cạnh
int maxpow; // Số mũ lớn nhất
int n, root; // Số nút, nút gốc
vector<canh> edge;
BangNhan() {}
BangNhan(int n, int root = 1)
{
init(n, root);
}
void init(int n, int root = 1)
{
this->n = n;
this->root = root;
maxpow = (int)log2(n) + 1;
depth.resize(n + 1);
head.resize(n + 1, 0);
edge.resize((n + 1) << 1);
st.resize(n + 1, vector<int>(maxpow + 1, -1));
cnt = 0;
}
void themCanh(int u, int v)
{
edge[++cnt] = {v, head[u]};
head[u] = cnt;
}
void dfs(int u, int fa)
{
depth[u] = (fa == -1) ? 0 : (depth[fa] + 1);
st[u][0] = fa;
for (int p = 1; p <= maxpow; p++)
{
st[u][p] = (st[u][p - 1] == -1) ? -1 : st[st[u][p - 1]][p - 1];
}
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if (v != fa)
{
dfs(v, u);
}
}
}
int lca(int x, int y)
{
if (depth[x] > depth[y])
swap(x, y);
int diff = depth[y] - depth[x];
for (int i = 0; i <= maxpow; i++)
if (diff & (1 << i))
y = st[y][i];
if (x == y)
return x;
for (int i = maxpow; i >= 0; i--)
{
if (st[x][i] != st[y][i])
{
x = st[x][i];
y = st[y][i];
}
}
return st[x][0];
}
};
struct KruskalTCT
{
vector<array<int, 3>> edges; // Danh sách cạnh vô hướng để xây dựng cây Kruskal
vector<int> parent; // Mảng cha cho Disjoint Set Union (DSU)
vector<int> head; // Con trỏ đầu của danh sách kề cho cây tái cấu trúc
vector<int> weight; // Trọng số của nút trên cây Kruskal tái cấu trúc
vector<canh> tree; // Đồ thị của cây Kruskal tái cấu trúc
int eid = 0;
int nodecnt; // Tổng số nút của cây Kruskal tái cấu trúc
int n, m;
KruskalTCT() {}
KruskalTCT(int n, int m, const vector<array<int, 3>>& _edges)
: edges(_edges), parent(2 * n + 1), head(2 * n + 1), tree(2 * n + 1), weight(2 * n + 1)
{
for (int i = 1; i <= n; i++)
parent[i] = i;
this->nodecnt = n;
this->n = n;
this->m = m;
xayDungLai();
}
void themCanh(int u, int v)
{
tree[++eid] = {v, head[u]};
head[u] = eid;
}
int tim(int x)
{
if (x != parent[x])
parent[x] = tim(parent[x]);
return parent[x];
}
bool cungTap(int x, int y)
{
return tim(x) == tim(y);
}
void xayDungLai()
{
sort(edges.begin() + 1, edges.end(), [](auto& a, auto& b)
{ return a[2] < b[2]; }); // Sắp xếp cạnh theo trọng số tăng dần
for (int i = 1; i <= m; i++)
{
auto [u, v, w] = edges[i];
int fu = tim(u), fv = tim(v);
if (fu != fv)
{
parent[fu] = parent[fv] = ++nodecnt;
parent[nodecnt] = nodecnt;
weight[nodecnt] = w;
themCanh(nodecnt, fu);
themCanh(nodecnt, fv);
}
}
}
pair<int, vector<canh>> layCay()
{
return {nodecnt, tree};
}
};
void giai()
{
int n, m;
cin >> n >> m;
vector<array<int, 3>> cacCanh(m + 1);
for (int i = 1; i <= m; i++)
{
auto& [u, v, w] = cacCanh[i];
cin >> u >> v >> w;
}
KruskalTCT kruskal(n, m, cacCanh);
auto [tongSoNut, dsCanh] = kruskal.layCay();
BangNhan bangNhan(tongSoNut);
bangNhan.edge = dsCanh;
bangNhan.head = kruskal.head;
bangNhan.cnt = kruskal.eid;
for (int i = 1; i <= tongSoNut; i++)
{
if (kruskal.tim(i) == i) // Có thể có nhiều cây Kruskal tái cấu trúc
{
bangNhan.dfs(i, -1);
}
}
int q;
cin >> q;
for (int i = 1; i <= q; i++)
{
int x, y;
cin >> x >> y;
if (!kruskal.cungTap(x, y))
{
cout << "impossible\n";
continue;
}
int lca = bangNhan.lca(x, y);
cout << kruskal.weight[lca] << endl;
}
}
Ví dụ 2: Life is a game (ICPC Shanghai Regional 2021)
Cho đồ thị vô hướng gồm n đỉnh và m cạnh, cùng q truy vấn. Mỗi truy vấn cho đỉnh xuất phát và kinh nghiệm ban đầu. Để đi qua một cạnh, kinh nghiệm hiện tại phải lớn hơn trọng số cạnh. Khi đi qua một đỉnh, điểm kinh nghiệm của đỉnh đó được cộng dồn vào kinh nghiệm hiện tại. Yêu cầu tìm kinh nghiệm tối đa có thể đạt được.
Các số màu đỏ là trọng số của nút trên cây Kruskal tái cấu trúc, tương ứng với giá trị lớn nhất nhỏ nhất trên đường đi (bottleneck). Các nút lá là các đỉnh của đồ thị gốc, số màu đen là điểm kinh nghiệm. Để tính toán thuận tiện, kinh nghiệm được cộng dồn từ nút lá lên nút gốc.
Đối với mỗi truy vấn, ta bắt đầu từ nút lá tương ứng, nhảy lên tổ tiên cho đến khi không thể nhảy được nữa (kinh nghiệm nhỏ hơn trọng số của nút). Đồng thời, ta đã tính trước tổng kinh nghiệm cho mỗi nút cha. Nhờ đó, ta chỉ cần kiểm tra từng bước nhảy: nếu kinh nghiệm hiện tại lớn hơn trọng số của nút đích thì mới nhảy.
struct canh
{
int to, next;
};
struct BangNhan
{
// ... (giống như ví dụ trên)
};
struct KruskalTCT
{
vector<array<int, 3>> edges;
vector<int> parent, head;
vector<int> weight; // Trọng số bottleneck của cạnh
vector<int> sumExp; // Tổng kinh nghiệm trong thành phần liên thông
vector<canh> tree;
int eid = 0;
int nodecnt;
int n, m;
KruskalTCT() {}
KruskalTCT(int n, int m, const vector<array<int, 3>>& _edges, vector<int>& _exp)
: edges(_edges), parent(2 * n + 1), head(2 * n + 1), tree(2 * n + 1), weight(2 * n + 1), sumExp(2 * n + 1)
{
this->nodecnt = n;
this->n = n;
this->m = m;
for (int i = 1; i <= n; i++)
sumExp[i] = _exp[i], parent[i] = i;
xayDungLai();
}
void themCanh(int u, int v)
{
tree[++eid] = {v, head[u]};
head[u] = eid;
}
int tim(int x)
{
if (x != parent[x])
parent[x] = tim(parent[x]);
return parent[x];
}
bool cungTap(int x, int y)
{
return tim(x) == tim(y);
}
void xayDungLai()
{
sort(edges.begin() + 1, edges.end(), [](auto& a, auto& b)
{ return a[2] < b[2]; });
for (int i = 1; i <= m; i++)
{
auto [u, v, w] = edges[i];
int fu = tim(u), fv = tim(v);
if (fu != fv)
{
parent[fu] = parent[fv] = ++nodecnt;
parent[nodecnt] = nodecnt;
sumExp[nodecnt] = sumExp[fu] + sumExp[fv];
weight[nodecnt] = w;
themCanh(nodecnt, fu);
themCanh(nodecnt, fv);
}
}
}
pair<int, vector<canh>> layCay()
{
return {nodecnt, tree};
}
};
void giai()
{
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 3>> cacCanh(m + 1);
vector<int> exp(n + 1);
for (int i = 1; i <= n; i++)
cin >> exp[i];
for (int i = 1; i <= m; i++)
{
auto& [u, v, w] = cacCanh[i];
cin >> u >> v >> w;
}
KruskalTCT kruskal(n, m, cacCanh, exp);
auto [tongSoNut, dsCanh] = kruskal.layCay();
BangNhan bangNhan(tongSoNut);
bangNhan.edge = dsCanh;
bangNhan.head = kruskal.head;
bangNhan.cnt = kruskal.eid;
for (int i = 1; i <= tongSoNut; i++)
{
if (kruskal.tim(i) == i)
bangNhan.dfs(i, -1);
}
int soMu = bangNhan.maxpow;
for (int i = 1; i <= q; i++)
{
int x, k;
cin >> x >> k;
int currentK = k;
bool tiepTuc = true;
while (tiepTuc)
{
bool capNhat = false;
for (int b = soMu; b >= 0; b--)
{
int cha = bangNhan.st[x][b];
if (cha != -1 && currentK + kruskal.sumExp[x] >= kruskal.weight[cha])
{
x = cha;
capNhat = true;
}
}
if (!capNhat)
tiepTuc = false;
}
cout << currentK + kruskal.sumExp[x] << endl;
}
}
Ví dụ 3: Hành trình trở về (NOI 2018)
Cho đồ thị vô hướng liên thông gồm n đỉnh, m cạnh. Mỗi cạnh có độ dài l và độ cao a. Có q truy vấn:
Truy vấn (x, y): Ban đầu có thể đi qua các cạnh có độ cao > y mà không mất chi phí (coi như lái xe). Tuy nhiên, xe không thể đi qua cạnh có độ cao <= y. Bạn có thể xuống xe tại bất kỳ đỉnh nào, và sau đó không được dùng xe nữa. Khi đi bộ, bạn phải trả chi phí bằng độ dài của mỗi cạnh (kể cả cạnh có độ cao > y). Yêu cầu tìm chi phí đi bộ nhỏ nhất để đi từ x đến đỉnh 1.
struct canh
{
int to, next;
};
struct BangNhan
{
// ... (giống như ví dụ 1)
};
struct KruskalTCT
{
vector<array<int, 3>> edges;
vector<int> parent, head;
vector<int> weight; // Trọng số bottleneck (độ cao)
vector<int> minDist; // Khoảng cách ngắn nhất đến đỉnh 1 trong thành phần
vector<canh> tree;
int eid = 0;
int nodecnt;
int n, m;
KruskalTCT() {}
KruskalTCT(int n, int m, const vector<array<int, 3>>& _edges, const vector<int>& dist)
: edges(_edges), parent(2 * n + 1), head(2 * n + 1), tree(2 * n + 1), weight(2 * n + 1), minDist(2 * n + 1)
{
this->nodecnt = n;
this->n = n;
this->m = m;
for (int i = 1; i <= n; i++)
minDist[i] = dist[i], parent[i] = i;
xayDungLai();
}
void themCanh(int u, int v)
{
tree[++eid] = {v, head[u]};
head[u] = eid;
}
int tim(int x)
{
if (x != parent[x])
parent[x] = tim(parent[x]);
return parent[x];
}
bool cungTap(int x, int y)
{
return tim(x) == tim(y);
}
void xayDungLai()
{
sort(edges.begin() + 1, edges.end(), [](auto& a, auto& b)
{ return a[2] > b[2]; }); // Sắp xếp theo độ cao giảm dần
for (int i = 1; i <= m; i++)
{
auto [u, v, w] = edges[i];
int fu = tim(u), fv = tim(v);
if (fu != fv)
{
parent[fu] = parent[fv] = ++nodecnt;
parent[nodecnt] = nodecnt;
minDist[nodecnt] = min(minDist[fu], minDist[fv]);
weight[nodecnt] = w;
themCanh(nodecnt, fu);
themCanh(nodecnt, fv);
}
}
}
pair<int, vector<canh>> layCay()
{
return {nodecnt, tree};
}
};
void giai()
{
int n, m;
cin >> n >> m;
vector<array<int, 3>> cacCanh(m + 1);
vector<vector<pair<int, int>>> ke(n + 1);
for (int i = 1; i <= m; i++)
{
auto& [u, v, a] = cacCanh[i];
int l;
cin >> u >> v >> l >> a;
ke[u].push_back({v, l});
ke[v].push_back({u, l});
}
vector<int> dist(n + 1, INF);
auto dijkstra = [&](int start)
{
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
vector<bool> visited(n + 1, false);
while (!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if (visited[u])
continue;
visited[u] = true;
for (auto [v, w] : ke[u])
{
if (dist[v] > d + w)
{
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
};
dijkstra(1);
KruskalTCT kruskal(n, m, cacCanh, dist);
auto [tongSoNut, dsCanh] = kruskal.layCay();
BangNhan bangNhan(tongSoNut);
bangNhan.edge = dsCanh;
bangNhan.head = kruskal.head;
bangNhan.cnt = kruskal.eid;
for (int i = 1; i <= tongSoNut; i++)
{
if (kruskal.tim(i) == i)
bangNhan.dfs(i, -1);
}
int q, k, s;
cin >> q >> k >> s;
int lastAns = 0;
int soMu = bangNhan.maxpow;
for (int i = 1; i <= q; i++)
{
int v0, p0;
cin >> v0 >> p0;
int v = (v0 + k * lastAns - 1) % n + 1;
int p = (p0 + k * lastAns) % (s + 1);
for (int b = soMu; b >= 0; b--)
{
int cha = bangNhan.st[v][b];
if (cha != -1 && kruskal.weight[cha] > p)
v = cha;
}
cout << kruskal.minDist[v] << endl;
lastAns = kruskal.minDist[v];
}
}