【1】做题心得 - 2024 NOIP #07 - T3【最小生成树】【离线】

ExFish · 2024-12-20 19:02:29 · 题解

题面在此。

\tt 2024/12/18 思路

我们发现这道题的 20 分数据范围为 n,m,q\leq 10^3,w\leq 10^9。

考虑直接跑 \tt Kruskal 重构一下。

这样，就成了一颗 \tt MST。

直接爽飞 \mathcal O(qn) 飞起。

\tt 2024/12/20 思路

重构了一下代码，通过。

我们发现查询可以简单离线下来。

先按照 w 对每一次查询进行排序。

我们发现，每一次 w 的改变，都会使得每一个国家的连通块变大。

我们考虑每一次 w 变化，都维护一个边指针连一下连通块。

因为前面已经 \tt MST 了，所以复杂度从 \mathcal O(m) 优化到 \mathcal O(n)。

还是相当简单的一道题呢。