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)$ 。沿用这种思想。从高到低考虑每一位，按照值分成两类。如果两类中都有点的话，那么它们之间一定会连一条边，并且两类会各成...
AtCoder3611 Tree MST
AtCoderLuogu分析点分治+$\mathrm{Kruskal}$。对于点分树上的每一个子树，只选取可能会出现的 $size$ 条边。具体就是，每次找到点分树中 $dis(root,u)+w[u]$ 最小的 $u$ ，然后其它的路径与它组合，并丢到候选边内即可。找到所有候选边后，跑一边$\mathrm{Kruskal}$求出答案即可。上面这么讲比较抽象，可以结合代码理解一下。代码//I...
AtCoder2134 Zigzag MST
AtCoderLuogu翻译分析首先这个连边的方式很毒瘤，要想办法改一下。可以发现，连了$(a,b)$、$(a+1,b)$、$(a+1,b+1)$三条边，与连了$(a,b)$、$(a,a+1)$、$(b,b+1)$三条边是等价的。于是每次加边就变成加了一条边和一个环。先来考虑环上的权值，设一个 $f[i]$ 表示 $i-1$ 到 $i$ 的最小边权。显然找到一个环上初始的 $f$ 最小的点，...
CF891C Envy
CodeForcesLuogu翻译分析考虑一个性质：对于一个图的所有 MST，每种边权的边的数量都相等。因此我们把每种边权的边拿出来单独考虑。我们把并查集恢复到加该种边以前的状态，然后判断这些边加进去会不会成环即可。现在的问题在于怎么把并查集恢复回去。显然可以可持久化并查集，但是有更优美的做法。预处理出每条边在加该种边权的边时两端点所在的连通块，这样子就很容易改回去了。代码//It is m...