题解：P14450 [ICPC 2025 Xi'an R] Directed Acyclic Graph

· · 题解

观察题目所给的性质：构造的图中点数较大，但是 m - n 较小，并且结点 1 能够到达所有结点。那么找出 DAG 中以 1 为根的外向生成树后，额外的边数量只有 m - n + 1 = 29 条（仅考虑第二个测试点）。不考虑单个点的可达点集的贡献时（这部分至多 n 个，远小于题目要求的 1.6 \times 10^4），题目对于 m - n 的限制显著强于单独对 n 的限制，所以只需要考虑在额外边数固定时，如何构造才能使不同可达点集合数量尽可能多。

首先给出一种较为容易的构造：取一个正整数 w，对于一行结点 a_1, a_2, \cdots, a_w，构造另一行结点 b_1, b_2, \cdots, b_w，使得 b_i 能够到达所有满足 j \neq i 的 a_j。这样可以构造出至少 2^w 个不同的可达点集，因为对于每个 a_i，都可以用 b_i 是否在所选的集合中来自由控制 a_i 是否在可达点集中。

朴素建出上面的图较劣。可以令额外的两行结点 p_1, p_2, \cdots, p_w 和 s_1, s_2, \cdots, s_w 分别可达 a 的一个前缀和一个后缀，从而优化所需要的额外边的数量。若取 w = 7，上述构造方案如下图所示：

例如 b_3 可达的点集如图中蓝色结点所示，包含 a_1, a_2, \cdots, a_w 中除了 a_3 之外的所有结点。该构造方案所需要的额外边数大约为 3w（注意还需要计算与 1 相连的边），即可以构造的集合数量为 \mathcal{O}(n + 2^{\frac{m - n}{3}})，还不足以通过此题。

考虑拓展上面的构造方案：记两个 d 行 w 列的点阵 a_{i, j} 和 b_{i, j}，其中每个 b_{i, j} 都可达 a 中所有点去掉某一列的一个前缀。例如，当 w = 7，d = 3 时，b_{i, 3} 的可达点集如下图所示：

这样可以构造出至少 (d + 1)^w 个不同的可达点集，因为对于每一列，都可以自由选择可达这列的一个后缀。类似地，可以令两行结点 p_1, p_2, \cdots, p_w 和 s_1, s_2, \cdots, s_w 分别可达前缀若干列和后缀若干列即可优化额外边的数量。

上述方案构造的图中需要 (d + 2) w + \mathcal{O}(1) 条额外边，取 d = 3 可以得到一个不同可达集合数量为 \mathcal{O}(n + 4^{\frac{m - n}{5}}) = \mathcal{O}(n + 2^{\frac{m - n}{2.5}}) 的构造方案，并且可以证明这取到了该方案的最优解，使用其他的 d 值或者每一列混合使用不同的点数量不会更优秀。

具体对于本题的数据范围，取 d = 3，w = 7 时最优，不同的可达集合数量至少为 4^7 = 16\,384。需要注意两行表示前缀和后缀的点中，边上的 1 个点可以优化掉，上述构造足以通过此题。