1 条题解
-
0
T3 城市生长(rebuild)题解
题意简述
有 个点的无向图, 条边按时间 依次加入。 次询问 :求最早的日期 ,使得加入所有 的边后, 所在连通块大小至少为 。不存在输出 , 时答案为 。
思路
离线加边与并查集
把所有边按 从小到大排序,依次加入,用并查集维护连通块大小。如果对每次询问都重新模拟一遍,复杂度是 ,无法通过。
我们需要一种能快速回答“ 所在连通块大小第一次达到 的时间”的结构。
Kruskal 重构树
在并查集合并两个连通块时,不直接合并,而是新建一个节点:
- 新节点的两个儿子分别是原来两个连通块的“代表节点”;
- 新节点的点权为当前边的建成时间 ;
- 新节点的子树大小为两个连通块大小之和。
如果一条边连接的两个点已经在同一个连通块中,就跳过这条边。最终得到一片森林,称为 Kruskal 重构树。原图的 个点是叶子,每次有效合并产生一个内部节点,所以总节点数不超过 。
这棵树有以下性质:
- 一个节点的子树恰好是某次合并后形成的一个连通块;
- 节点的点权是形成这个连通块时最后加入的那条边的时间;
- 从叶子 往根走,子树大小严格递增,点权单调不降。
回答询问
对于询问 :
- 若 ,答案为 ;
- 若 所在 Kruskal 树的根节点子树大小都小于 ,说明 的连通块永远达不到 ,输出 ;
- 否则,从叶子 往上找最后一个子树大小小于 的祖先 。那么 的父亲就是第一个子树大小 的祖先,它的点权就是答案。
“最后一个满足条件的祖先”可以用倍增在 时间内找到:从高位到低位尝试跳,若跳到的祖先子树大小仍小于 ,就跳过去。
正确性证明
引理 1: 对任意节点 , 的子树恰好是某个时刻的一个连通块。
对合并次数归纳。叶子是初始的单个点连通块。每次新建节点时,它的两个儿子分别是当前两个连通块的代表,子树并起来就是合并后的连通块。
引理 2: 从叶子 到根的路径上,子树大小严格递增,点权单调不降。
每次合并至少把两个非空连通块合并,所以大小严格增加。边按时间排序后处理,后创建的节点点权不小于先创建的节点点权。
引理 3: 设 是 到根路径上第一个子树大小 的节点,则 是 的连通块第一次达到大小 的日期。
在 这一天, 所代表的连通块已经形成,且大小 。而在 之前, 所在的连通块是 的某个后代(或 自己),其大小都小于 。因此第一次达到 的日期就是 。
定理: 算法输出正确。
若根的大小都小于 ,则任何时刻 的连通块都达不到 ,输出 正确。否则由引理 3,倍增找到的第一个大小 的祖先的点权就是答案。 时不需要加边,答案为 。
复杂度
排序 ;并查集 ;倍增预处理 ;每次询问 。
总时间复杂度 ,空间复杂度 。
参考代码(C++)
#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct Edge { int t, u, v; bool operator<(const Edge &o) const { return t < o.t; } }; int main() { freopen("rebuild.in", "r", stdin); freopen("rebuild.out", "w", stdout); int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; vector<Edge> edges(m); for (int i = 0; i < m; i++) scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].t); sort(edges.begin(), edges.end()); int maxNodes = 2 * n + 5; vector<int> dsu(maxNodes), sz(maxNodes), par(maxNodes, 0), weight(maxNodes, 0); for (int i = 1; i <= n; i++) { dsu[i] = i; sz[i] = 1; weight[i] = 0; } auto find = [&](int x) { int r = x; while (dsu[r] != r) r = dsu[r]; while (dsu[x] != x) { int y = dsu[x]; dsu[x] = r; x = y; } return r; }; int tot = n; for (const Edge &e : edges) { int ru = find(e.u), rv = find(e.v); if (ru == rv) continue; ++tot; dsu[ru] = dsu[rv] = tot; dsu[tot] = tot; par[ru] = par[rv] = tot; weight[tot] = e.t; sz[tot] = sz[ru] + sz[rv]; } int LOG = 1; while ((1 << LOG) <= tot) LOG++; vector<vector<int>> up(LOG, vector<int>(tot + 1, 0)); for (int v = 1; v <= tot; v++) up[0][v] = par[v]; for (int j = 1; j < LOG; j++) for (int v = 1; v <= tot; v++) up[j][v] = up[j - 1][up[j - 1][v]]; while (q--) { int u, k; scanf("%d %d", &u, &k); if (k <= 1) { puts("0"); continue; } int root = find(u); if (sz[root] < k) { puts("-1"); continue; } int v = u; for (int j = LOG - 1; j >= 0; j--) { int a = up[j][v]; if (a != 0 && sz[a] < k) v = a; } printf("%d\n", weight[par[v]]); } return 0; }易错点
- 要特判输出 :此时不需要任何道路,不能去重构树上找祖先。
- 询问只与 有关:题目不是问 和 何时连通,而是问 所在连通块何时达到大小 ,不要读错题意。
- 重边与相同时间:连接同一连通块内部的边直接跳过;相同时间的多条边可以任意顺序处理,答案的日期不变。
- 重构树可能是一条深度为 的链:例如路径图按 的顺序加边。不能递归 DFS,也不能暴力爬父亲,要用倍增。
- 数组要开到 :每次有效合并新建一个节点,总节点数最多 。
- 并查集根与重构树根:代码中
find(u)返回的是最终连通块的 DSU 根,也是重构树的根;par数组才是重构树的父亲指针,两者不要混用。 - :此时所有点都是孤立的, 的询问全部输出 。
测试点设计
测试点 设计意图 1 样例 1,基本加边与询问 2 样例 2,两个互不连通的连通块,检验 3 ,检验 与无解 4 ,大量 与 询问 5 的链,边权递增,检验连通块向两侧生长 6 的链,所有边同一天建成,检验相同时间处理 7 随机图 ,随机时间与询问 8 随机图 ,大量连通块与随机询问 9 随机树 ,边权为随机排列 10 路径图 ,边权递增,重构树退化为深链,检验倍增 11 两个互不连通的大连通块,大量跨块询问输出 12 连通图 ,所有边同一天建成,答案只有 和该日期
- 1
信息
- ID
- 8
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者