洛谷6628 [省选联考 2020 B 卷]丁香之路
LuoguLOJ分析走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。时间复杂度 $...
标签 生成树 下的文章
- 首页
- 生成树
UOJ236 【IOI2016】railroad
UOJLuogu分析我们把速度看成点，铁路看成边，相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路，且加入的边从大到小连边的边数最小。既然要存在欧拉回路，那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上，然后根据每个点两个方向被覆盖的次数连一些边即可。然而欧拉回路还需要连通，所以我们还要求个 MST 把...
LOJ576 「LibreOJ NOI Round #2」签到游戏
LOJ分析设 $s_i$ 为 $\sum_{j=1}^i b_j$，则一次询问可以确定 $s_r-s_{l-1}$。如果我们看成连边 $(l-1,r)$，则相当于要让 $(0,n)$ 连通，也就是要求最小生成树。根据 Kruskal 那套理论，我们一定会连边 $(0,n)$。根据 Prim 那套理论，剩下的点要么连 $(0,i)$，要么连 $(i,n)$。更具体的，一定存在一个点 $p$ 满...
AtCoder Regular Contest 076 简要题解
比赛地址Reconciled?如果 $\lvert n-m\rvert>1$ 一定无解。否则，如果 $n=m$ 则答案为 $2\times n!\times m!$，如果 $\lvert n-m\rvert =1$ 则答案为 $n!\times m!$。代码Built?和某个切比雪夫距离最短路的题很像。对于每个点 $(x,y)$，向 $x$、$y$ 各连一条 $0$ 边。然后再把相邻两...
洛谷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...