P15241 [NHSPC 2025] 资料中心

世界上最大的云端基础设施供应商 HyperNet 公司正在建置下一代分布式数据中心，该公司在世界各地建立了 $n$ 套云端主机，编号 $1, 2, \ldots, n$，主机之间通过 $m$ 条光纤 $K = \{K_1, K_2, \ldots, K_m\}$ 相互串联，每条光纤线路 $K_i = (u_i, v_i)$ 必定连接两台不同的主机 $(1 \leq u_i, v_i \leq n, u_i \neq v_i)$，且该光纤网络维护成本为正整数 $w_i$ 。这个庞大的分布式网络未来将支撑着全球的数据交换、AI 模型训练与实时服务。 但是为了应对能源短缺与日益严峻的网络攻击，HyperNet 决定采用动态连线策略，也就是光纤线路 $K_i$ 只能在特定时段内 $[l_i, r_i), 0 \leq l_i < r_i \leq d$ 可以被开启（但并非一定要被开启），以降低耗能与暴露面。然而，这导致网络在不同时段的拓扑不再固定，有时甚至可能分裂成多个孤立的网段。 为了确保所有的主机都能互通消息，数据中心安全控制中心（简称安控中心）需要在每一个满足 $0 \leq i < d$ 的时间点 $i$ 从可以被开启的光纤线路 $K' \subseteq K$ 中，自动决定应开启哪些光纤线路 $K'' \subseteq K'$，使得所有主机都能互通且这些被开启的光纤线路维护成本加总后为最低。 举例来说，若总共有 $5$ 台主机 $(s_1, s_2, s_3, s_4, s_5)$，及 $5$ 条光纤线路 $(K_1, K_2, K_3, K_4, K_5)$。每条光纤连接的主机、维护成本及可开启时段如下所示： - $K_1 = (s_1, s_2), w_1=5$，且能开启时段为 $[0, 4)$ - $K_2 = (s_2, s_3), w_2=1$，且能开启时段为 $[0, 4)$ - $K_3 = (s_4, s_5), w_3=3$，且能开启时段为 $[2, 6)$ - $K_4 = (s_5, s_1), w_4=1$，且能开启时段为 $[1, 5)$ - $K_5 = (s_2, s_5), w_5=2$，且能开启时段为 $[3, 6)$ 则： - 在时间点 $0$ 时，可被开启光纤线路有 $K_1, K_2$，即使全部开启仍无法连上 $s_4, s_5$, 因此在时间点 $0$ 时无法让所有主机都被连通。 - 在时间点 $2$ 时，可被开启光纤线路有 $K_1, K_2, K_3, K_4$，全部开启即可将 $5$ 台主机都连通，总维护成本为 $5+1+3+1=10$。 - 在时间点 $3$ 时，可被开启光纤线路有 $K_1, K_2, K_3, K_4, K_5$，若开启 $K_2, K_3, K_4, K_5$，维护成本为 $1+3+1+2=7$；若开启其他线路组合，维护成本皆大于 $7$。 - 其他时段皆无法让所有主机被连通。

$$ \begin{aligned} &n \; m \; d \\ &u_1 \; v_1 \; w_1 \; l_1 \; r_1 \\ &u_2 \; v_2 \; w_2 \; l_2 \; r_2 \\ &\vdots \\ &u_m \; v_m \; w_m \; l_m \; r_m \end{aligned} $$ - $n$ 为节点数。 - $m$ 为边数。 - $d$ 为时间点的上限。 - $u_i, v_i, w_i, l_i, r_i$ 代表有一条连接主机 $u_i$ 与主机 $v_i$、维护成本 $w_i$ 的光纤线路，可以在时段 $[l_i, r_i)$ 被开启。

$$ \begin{aligned} &a_0 \; a_1 \; a_2 \; \ldots \; a_{d-1} \end{aligned} $$ - $a_i$ 代表在时间点 $i$ 将 $n$ 台主机都连通的最小维护成本。若该时间点无法让主机连通则 $a_i = -1$。

### 数据限制 - $1 \leq n \leq 10^5$。 - $1 \leq m \leq 3 \times 10^5$。 - $1 \leq d \leq 3 \times 10^5$。 - $1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$。 - $1 \leq w_i \leq 10^9$。 - $0 \leq l_i < r_i \leq d$。 - 输入的数皆为整数。 ### 评分说明 本题共有五组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 5 | $d=1$。 | | 2 | 9 | $n \leq 100$, $r_i = d$。 | | 3 | 21 | $r_i = d$。 | | 4 | 26 | $w_i = 1$。 | | 5 | 39 | 无额外限制。 |