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 | 無額外限制。 |