P15241 [NHSPC 2025] Data Center

HyperNet, the world’s largest cloud infrastructure provider, is building the next generation of distributed data centers. The company has deployed $n$ cloud hosts around the world, numbered $1, 2, \ldots, n$. The hosts are interconnected by $m$ fiber links $K = \{K_1, K_2, \ldots, K_m\}$. Each fiber link $K_i = (u_i, v_i)$ connects two different hosts $(1 \leq u_i, v_i \leq n, u_i \neq v_i)$, and has a positive integer maintenance cost $w_i$. This huge distributed network will support global data exchange, AI model training, and real-time services in the future. However, to deal with energy shortages and increasingly serious cyberattacks, HyperNet decides to use a dynamic connectivity strategy. That is, each fiber link $K_i$ can only be turned on during a specific time interval $[l_i, r_i), 0 \leq l_i < r_i \leq d$ (but it does not have to be turned on), in order to reduce energy usage and the attack surface. As a result, the network topology is no longer fixed at different times, and it may even split into multiple isolated segments. To ensure that all hosts can communicate with each other, the data center security control center needs, at every time point $i$ satisfying $0 \leq i < d$, to automatically decide which fiber links $K'' \subseteq K'$ to turn on from the set of links that can be turned on $K' \subseteq K$, so that all hosts can communicate with each other and the total maintenance cost of the turned-on links is minimized. For example, suppose there are $5$ hosts $(s_1, s_2, s_3, s_4, s_5)$ and $5$ fiber links $(K_1, K_2, K_3, K_4, K_5)$. The endpoints, maintenance costs, and available time intervals are as follows: - $K_1 = (s_1, s_2), w_1=5$, and it can be turned on during $[0, 4)$. - $K_2 = (s_2, s_3), w_2=1$, and it can be turned on during $[0, 4)$. - $K_3 = (s_4, s_5), w_3=3$, and it can be turned on during $[2, 6)$. - $K_4 = (s_5, s_1), w_4=1$, and it can be turned on during $[1, 5)$. - $K_5 = (s_2, s_5), w_5=2$, and it can be turned on during $[3, 6)$. Then: - At time point $0$, the links that can be turned on are $K_1, K_2$. Even if all of them are turned on, $s_4, s_5$ still cannot be connected, so it is impossible to make all hosts connected at time point $0$. - At time point $2$, the links that can be turned on are $K_1, K_2, K_3, K_4$. Turning on all of them connects all $5$ hosts, with total maintenance cost $5+1+3+1=10$. - At time point $3$, the links that can be turned on are $K_1, K_2, K_3, K_4, K_5$. If we turn on $K_2, K_3, K_4, K_5$, the maintenance cost is $1+3+1+2=7$; any other combination of links has a maintenance cost greater than $7$. - At all other times, it is impossible to connect all hosts.

$$ \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$ is the number of nodes. - $m$ is the number of edges. - $d$ is the upper bound of time points. - $u_i, v_i, w_i, l_i, r_i$ mean that there is a fiber link connecting host $u_i$ and host $v_i$ with maintenance cost $w_i$, and it can be turned on during the interval $[l_i, r_i)$.

$$ \begin{aligned} &a_0 \; a_1 \; a_2 \; \ldots \; a_{d-1} \end{aligned} $$ - $a_i$ is the minimum maintenance cost to connect all $n$ hosts at time point $i$. If it is impossible to connect the hosts at that time point, then $a_i = -1$.

### Constraints - $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$, and $u_i \neq v_i$. - $1 \leq w_i \leq 10^9$. - $0 \leq l_i < r_i \leq d$. - All input values are integers. ### Scoring This problem has five subtasks, with the constraints as follows. Each subtask may contain one or more pieces of testdata. You will get the score for a subtask only if you pass all testdata in that subtask. | Subtask | Score | Additional Input Constraints | | :-----: | :---: | ---------------------------- | | 1 | 5 | $d=1$. | | 2 | 9 | $n \leq 100$, $r_i = d$. | | 3 | 21 | $r_i = d$. | | 4 | 26 | $w_i = 1$. | | 5 | 39 | No additional constraints. | Translated by ChatGPT 5