ZigZagK的博客
[思维+最大生成树]Codeforces1408E【Avoid Rainbow Cycles】题解
题目概述CF1408E解题报告呜呜呜,这就是个沙雕题,但是我不会。如果多个集合之间的边组成了环说明就有彩虹路,但是显然我们不可能把一个集合中的所有边建出来。考虑建辅助点,自然而然我们想到对于每个...
[Kruskal重构树+ST表]LOJ2718(NOI2018)【归程】题解
题目概述给出 $n$ 个点 $m$ 条无向边的连通图,每条边有距离和高度,如果高度 $\le$ 水的高度这条边就会被淹没,令 $dis_i$ 表示到达 $1$ 号点的最短路,问从 $x$ 点出发...
[Kruskal重构树]BZOJ3732【Network】题解
题目概述给出一张无向图,多次询问两个点之间最长边的最小值为多少。解题报告因为最小生成树神奇的性质,我们只需要建出最小生成树然后求最小生成树路经上的最长边就是答案。不过我是来写Kruskal重构树...