洛谷4768 [NOI2018]归程
Luogu分析考虑把边按海拔从大到小排序并建 Kruskal 重构树。每个询问从 $v$ 往上倍增找到最浅的 $a>p$ 的点 $u$，则子树 $u$ 中的点是可以开车到达的，找一个到 $1$ 的距离最小的点即可。一遍 Dijkstra（关于 SPFA：它死了）预处理出每个点到 $1$ 的最短路，在重构树上维护子树最值即可。代码// ==========================...
标签 生成树 下的文章
- 首页
- 生成树
洛谷2619 [国家集训队]Tree I
Luogu分析设 $f(x)$ 为恰好选 $x$ 条白边的答案。容易发现 $f(x)$ 是凹的。考虑 WQS 二分。二分斜率 $m$，则我们需要最小化截距 $b=f(x)-mx$。把每条白边的权值减去 $m$ 即可求出 $b$ 的最小值，再根据此时最多选出的白边数调整二分上下界即可。代码// ==================================== // author: ...
CF603E Pastoral Oddities
CodeforcesLuogu分析首先有一个结论：一个大小为偶数的连通块一定存在一个合法的边集，一个大小为奇数的连通块一定不存在一个合法的边集。证明：如果连通块大小为奇数，又因为每个点度数都为奇数，所以总度数为奇数，这是不可能的。如果连通块大小为偶数，此时我们可以先找到一棵生成树，从下往上构造即可。可以发现一定能构造出解。于是我们只需要保证图中没有大小为奇数的连通块即可。考虑一个类似 Kru...
CF1245D Shichikuji and Power Grid
CodeforcesLuogu分析新建一个点 $0$ 表示建电站。从 $0$ 向每个点 $i$ 连边权为 $c_i$ 的边；$i,j\;(0,j>0)$ 之间连边权为 $\operatorname{dis}(i,j)\times(k_i+k_j)$ 的边。那么最小生成树即为答案。正确性显然。输出方案根据最小生成树上的边搞一搞就好了。代码// ======================...
LOJ2876 「JOISC 2014 Day2」水壶
LOJ分析这题有很多种讲法...「AMPPZ2014」Petrol 放到网格图上。求出离每个格子最近的建筑，然后对于每对相邻的最近建筑不相同的原野，在它们的最近建筑间连一条边权为距离的边，然后就变成了「NOIP2013」货车运输。求出离每个格子最近的建筑，然后对于每对相邻的最近建筑不相同的原野，在它们的最近建筑间连一条边权为距离的边，然后建出 Kruskal 重构树，每次询问 LCA 的点权...
BZOJ5216 [Lydsy2017省队十连测]公路建设
BZOJ分析考虑一个很暴力的思路。以边的编号为下标建一棵线段树，每个节点开一个 vector 存一下对应区间内哪些边在最小生成森林内。这样子合并两个节点就是先 std::merge 得到排好序的边集，然后 Kruskal 求最小生成森林。查询就把每个区间合并起来就好了。然后它压着时限过了...代码// =================================== // auth...
BZOJ3714 [PA2014]Kuglarz
BZOJ分析感觉这题的建模好妙啊...设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。考虑到如果询问了 $[i,j]$，那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。因此考虑这样一个模型：对于每个区间 $[i,j]$ ，在 $i-1$ 和 $j$ ...
洛谷1967 货车运输
Luogu分析把边从大到小排序后建出 Kruskal 重构树。那么答案就相当于 Kruskal 重构树上 LCA 的权值。随便用什么办法求 LCA 即可。注意原图可能不连通，询问时要判一下连通性，而且预处理时每个连通块都要预处理到。代码// =================================== // author: M_sea // website: http://...
CF875F Royal Questions
CodeForcesLuogu题意因为Luogu上那个翻译过于晦涩，所以附上一份䕀来的翻译：有 $N$ 个王子和个 $M$ 个公主，每个公主或王子都只能选择至多一个王子或公主作为自己的结婚对象（王子选择公主，公主选择王子）。每个公主有且仅有两个中意的王子 $a,b$ ，她只会至多选择其中一个作为自己的结婚对象，而如果某个公主选择了自己的结婚对象，就会给出 $w$ 的嫁妆。求在满足所有公主的条...
CF888G Xor-MST
CodeForcesLuogu翻译分析$\mathrm{Boruvka}$ + $\mathrm{Trie}$ 。你可能没有听说过前面那个算法。它用来求 $\mathrm{MST}$ ，每次对于每个连通块找到一条最小边，然后连上。可以发现时间复杂度为 $O(n\log n)$ 。沿用这种思想。从高到低考虑每一位，按照值分成两类。如果两类中都有点的话，那么它们之间一定会连一条边，并且两类会各成...