LuoguLOJ分析走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数,这个条件长得很像欧拉回路。我们首先把 $m$ 条关键边连上,然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点,显然相邻的两个间连一条边是最优的。这样子满足了度数限制。但是我们还需要让图连通。我们把所有连通块缩成一个点,然后求最小生成树,那么可以花费最小生成树上边权和的两倍的代价让图连通起来。时间复杂度 $...
UOJLuogu分析我们把速度看成点,铁路看成边,相当于加上 $+\infty\to -\infty$ 和若干条边后让图存在欧拉回路,且加入的边从大到小连边的边数最小。既然要存在欧拉回路,那么相邻的两个点从左往右和从右往左被经过的次数应该是一样的。于是我们先把 $s_i\to t_i$ 连上,然后根据每个点两个方向被覆盖的次数连一些边即可。然而欧拉回路还需要连通,所以我们还要求个 MST 把...
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$ 满...
比赛地址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$ 边。然后再把相邻两...
Luogu分析考虑把边按海拔从大到小排序并建 Kruskal 重构树。每个询问从 $v$ 往上倍增找到最浅的 $a>p$ 的点 $u$,则子树 $u$ 中的点是可以开车到达的,找一个到 $1$ 的距离最小的点即可。一遍 Dijkstra(关于 SPFA:它死了)预处理出每个点到 $1$ 的最短路,在重构树上维护子树最值即可。代码// ==========================...
Luogu分析设 $f(x)$ 为恰好选 $x$ 条白边的答案。容易发现 $f(x)$ 是凹的。考虑 WQS 二分。二分斜率 $m$,则我们需要最小化截距 $b=f(x)-mx$。把每条白边的权值减去 $m$ 即可求出 $b$ 的最小值,再根据此时最多选出的白边数调整二分上下界即可。代码// ==================================== // author: ...
CodeforcesLuogu分析首先有一个结论:一个大小为偶数的连通块一定存在一个合法的边集,一个大小为奇数的连通块一定不存在一个合法的边集。证明:如果连通块大小为奇数,又因为每个点度数都为奇数,所以总度数为奇数,这是不可能的。如果连通块大小为偶数,此时我们可以先找到一棵生成树,从下往上构造即可。可以发现一定能构造出解。于是我们只需要保证图中没有大小为奇数的连通块即可。考虑一个类似 Kru...
CodeforcesLuogu分析新建一个点 $0$ 表示建电站。从 $0$ 向每个点 $i$ 连边权为 $c_i$ 的边;$i,j\;(0,j>0)$ 之间连边权为 $\operatorname{dis}(i,j)\times(k_i+k_j)$ 的边。那么最小生成树即为答案。正确性显然。输出方案根据最小生成树上的边搞一搞就好了。代码// ======================...
LOJ分析这题有很多种讲法...「AMPPZ2014」Petrol 放到网格图上。求出离每个格子最近的建筑,然后对于每对相邻的最近建筑不相同的原野,在它们的最近建筑间连一条边权为距离的边,然后就变成了「NOIP2013」货车运输。求出离每个格子最近的建筑,然后对于每对相邻的最近建筑不相同的原野,在它们的最近建筑间连一条边权为距离的边,然后建出 Kruskal 重构树,每次询问 LCA 的点权...
BZOJ分析考虑一个很暴力的思路。以边的编号为下标建一棵线段树,每个节点开一个 vector 存一下对应区间内哪些边在最小生成森林内。这样子合并两个节点就是先 std::merge 得到排好序的边集,然后 Kruskal 求最小生成森林。查询就把每个区间合并起来就好了。然后它压着时限过了...代码// =================================== // auth...