WC2025 游记

tkdqmx · 2025-01-17 21:06:16 · 生活·游记

更好的阅读体验

Day 0 晚上 开幕式

上午坐飞机到深圳，大概 11:30 碰到了接机的工作人员，但是坐同一班车到一中的有两个成都的同学飞机晚点了，为了等他们 12:30 才坐上车，差点没吃上饭...

下午在寝室做了道网络流，看了看第二天的讲义，就没做什么了，等着晚上吃完饭后的开幕式。

开幕式的节目没什么好说的，引用 gm 的原话：

节目有点不伦不类，川剧，古代服饰，沂蒙山歌，和绍兴有啥关系，没得江南水乡的半点意思，不是绍剧，是苕皮。

确实硬把川剧《变脸》说成是绍剧《千变万化》有点难绷，但好在质量还行。

中间听浙江两位领导的致辞就相当于白听，全是空话，不做点评，杜子德教授的讲话还行，讲了一下他自己的经历，和自己的爱国之情从何而来，还是挺令人动容的，也比较幽默风趣，不死板，在讲他读书经历时令人印象深刻的一句话：

天天听说社会主义一定会打败资本主义，我觉得不一定。

开幕式完了过后 gm 就过来把手机收了，但其实电脑一样能用，没啥太大影响，走的时候他说第二天能听懂多少算多少，因为那些人讲课多半都听不懂，一下就熄灭了我听课的欲望，只能自求多福了。

Day 1 上午 浅谈非确定性算法——周康阳

起床铃是《一剪梅》变奏有点六，线性代数没学好，就只挑几道能听懂的题写总结吧。

CF1746F Kazaee

先离线下来，将每个值随机替换为 0/1，判断和是否为 k 倍数，每次正确性至少为 \frac{1}{2}，重复做 40 次即可。

正确性证明：对于其中一个不满足的数，设它出现次数为 w ，现在求出的除该数外的数和为 S，则 S 和 S+w，至少有一个不为 k 的倍数，而两种状态被选取的概率均为 \frac{1}{2}，所以单次的正确率至少为 \frac{1}{2}，跑 40 次即可满足正确性要求。

NOI2013 向量内积

考虑随机选取集合 S，对于每个 i，与 S 的总和做内积，和上一道一样，每次正确性至少为 \frac{1}{2}，跑 40 次即可。

[zky 原创题]()

题目大意：给定一个长为 n 的序列，要求完成两个操作：1.区间反转；2.查询区间子集最大异或和。

zky 的做法：维护 100 个序列，对于每个序列的第 i 个数，有 \frac{1}{2} 的概率为 a_i，有 \frac{1}{2} 的概率为 0，查询时对每个序列做异或和，然后假装这些元素的线性基为原区间的线性基。

实做的话理论上应该是用平衡树/线段树维护，但是 100 个序列有点超模，个人觉得不需要维护那么多，毕竟时空可能不太够，正确性被保证也用不到那么多序列。

Day 1 下午 图论与连通性问题选讲——沈吉滪

还是挑听得懂的题，毕竟像虚树之类的知识点没学过...

QOJ4809 Maximum Range

题目大意：无向图找边不重复的环，最大化最大边权减最小边权，需构造方案（n \leq 1e5）。

做法：答案取每个边双的最大边减最小边的最大值，化边为点跑最大流找方案。

SWTR-8 地地铁铁

先考虑单个点双内，显然只能经过点双内的点，若颜色均相同则显然不计入答案，否则最多只有一对点不计入答案：只有两个点连着两种不同的边时的这两个点；

对于不在同一点双内的两个点，只有中间有异色点双即可计入答案，建圆方树跑点分治即可。

[耳分解定义]()

若对于图 G 的一个子图 G'=(V',E')：

若存在简单路径/简单环 x_1 -> x_2 -> ... -> x_k，使得有且仅有 x_1 和 x_k 属于 V' ，则称该路径 P 为 G 关于 G' 的开耳。

若一个无向图 G 可以从一个只包含一个点的子集 G' 开始，不断加入 (G,G') 的开耳得到图 G，则称 G 可被耳分解。

一张有向图可耳分解当且仅当强连通时，一张无向图可耳分解当且仅当边双连通时。

SNOI2013 Quare

状压耳分解，f_{s,i,j} 表示加上 G' 后的集合，现在走到的点 i，要去的终点为 j 的最小权值。

[切边等价定义]()

在一个边双连通图中，定义两条切边等价当且仅当在 G 的任何一个简单环中这两条边要么同时出现，要么同时不出现。

定义等价于在 G 中删去这两条边后 G 不连通，等价于在 G 的任意一棵生成树 T 中，假设 e_1，e_2 为树边，不存在任何一条非树边跨过其中一条边而不跨过另一条边。

求等价类时，考虑为每条非树边设置一个随机权值，定义树边的权值为所有跨过它的非树边的权值异或和，显然这是一个非确定性算法，但正确率很高，且确定性算法复杂度较高，所以该算法适用面更广。

对于树边，若权值为 0，则为割边，并可按权值划分等价类，权值计算可以通过树上差分完成。

ICPC2015 WF Tours

首先如果对于一个由多个简单环组成的环，若组成它的简单环均满足条件则它一定满足条件，我们就不用处理这种环，接下来考虑对于两个起点只出现一次的简单环 A，B，可以知道 A \oplus B 也必须要满足条件，将这三个环拆分成 A \cap B，A - A\cap B 和 B - A\cap B，可以证明 A，B 和 A \cap B 都是其中两个拆分的合并，接下来按此递归直到所有的边集无交，随后答案就是这些边集大小 \gcd 的因数，而两条边在同一边集的条件就是在所有的简单环内必须同时出现/不出现，刚好就是切边等价类。

Day 1 晚上 狼人杀混战

全程处在 1 号位，且三把女巫第一晚都救人了，而且三把我都赢了（写到后面想起来有这一个事）

[第一把 9 人标准带警徽]()

拿了把狼，警上接杀起跳给警下好人发金水，但是后置位好人认我？？？

虽然说最后警徽投给了真预言家，但是警下成功把他 gank 出去了，结果警徽又飞给了我发的金水？？？

后面两天我没吃刀，竟然好人还信我，那没办法只能绑票赢下了。

[第二把 10 人狼王守卫带警徽]()

拿了张民，5 给 10 发金，8 给我发金，到我发言给警下喊话平票 PK，但是 3 票飞给了 5 号？？？

警下 3 号拍守卫要求抗推 5 号，但最后 8 号被抗推，晚上 5 号倒牌，警徽飞给 10（两人的第一警徽流都是 2），但我明锐地注意到法官没确认狼王开枪手势，在这种情况下没人开枪，于是得出了狼王没参与对跳的惊人结论！！！（但实际是 5 狼王压枪做身份了）

最后在第二天白天抗推了一张划水牌，第三天白天起来 6 10 双倒，3 号单边守卫喊了一声拍刀？？？（但其实此时狼队只剩他一人，拍刀啥都没有而且并没有找到女巫位置，但是 6 号守卫第二天没对跳是被闷死的，所以如果 3 不排刀狼队理论上必赢的，狼坑 3 5 10）

[第三把 9 人标准不带警徽]()

又拿狼了，第一天顺时针首置位发言索性划水过，然后震惊的事情来了：2 给 5 发金，5 给 8 发杀，8 号发言说 9 一定会起跳，9 起跳给 7 发了查杀（这把狼坑 1 6 7），8 号猎人出局开枪带 7，晚上操控狼队刀 9，女巫没开药。

第二天晚上刀完人过后你们不知道我笑得多开心，要不是 9 号验了张杀出来第一天就得走 3 个好人，但是验出来了也没关系，我还有 2 5 两个裸的抗推位，最后 2 5 平票 PK，我怕平安日直接压了手没有投票，最后 2 出局屠神获胜。

最后复盘是这个样子：2 号女巫给 5 银水发金水这里没问题，但 5 信了 2 是真预于是选择了滴滴代跳往后诈 8 身份，9 真预没办法也说不了什么，所以其实 2 5 的逻辑都是没有问题的，但他们撞一起就出大问题了，我这只狼也只能跟着好人躺赢了。

Day 2 上午 AI时代的编程新范式——郑勤锴

今天上午第一课堂人起码少了一半，好像对这个感兴趣的人很少...

[图灵完备]()

1.无限长的纸带：每个格子上写一个字符；2.字符表：所有可能出现的字符；3.读写头：可以读取/删除/写入字符；4.状态寄存器：存放计算机的运行/终止状态；5.指令集：读写头在一定条件下的行为，即程序。

图灵完备语言：C++，Python，Java 等；非图灵完备语言：Latex，Markdown，HTML 等。

后面在讲神经网络模型和大模型的训练，听不懂了就不听补昨天的游记去了...

CodeGeeX

其实最后讲到 CodeGeeX 的时候还是很有感触的，毕竟用了快一年了，去个人中心看了一下累计采纳建议已经 2000+ 次了，还是在我的 OI 生涯上提供了挺大帮助的，感谢 TKU。

思维型题目选讲——郭羽冲

思维型题目还是不太适合我，只能随便找一道勉强听懂的题了...

CF1806F(1+2) GCD Master

相当于将所有数划分为 n-m 个集合，使得这些集合各自 \gcd 的和最大。

考虑若有两个集合满足 \max(S)-\min(S) > 0，则对于其中任意一个集合满足 \gcd(S)\cdot 2 \leq \max(S)，所以若将 \max(\max(S_1),\max(S_2)) 单独作为一个集合，剩下的所有数作为一个集合一定是不劣的，所以这样的集合最多出现一个。

接下来将合并相等/不等元素看作两种不同的操作，枚举后者进行的次数 t，此时前者的代价即为每种元素去掉一个后前 m-t 小的和。

此时问题转化为：在元素互不相等的集合中选出 t+1 个元素使得 sum(S)-\gcd(S) 最小，将元素从小到大排列为 a_1...a_n，若 i<j<k 且 a_i \notin S， a_j\in S，a_k \in S，则 gcd(S) \leq a_k-a_j，将 a_k 换成 a_i 后 gcd(S) 最多增加 a_k-a_j，但 sum(S) 会减少 a_k-a_i>a_k-a_j，所以一定不劣，即最后选出的序列一定形如 a_1...a_t，a_p，其中 t+1\leq p\leq n。

对每个 t，若 \gcd(a_1...a_t)=\gcd(a_1...a_{t+1}) 则 p=t+1 时最优，根据 \gcd 函数的性质可以得出这种情况最多出现 \log V 次，对这部分的 t 暴力计算就可以了，时间复杂度 O(n \log^2 V)。

Day 3 白天 WC2025

100+50+40=190，pretest 和最终结果同分，今年虽然开始有 pretest 了不错，但是题出得稀烂，区分度基本等于没有...

[WC2025 猫粮]()

为什么是猫粮，我想看的明明是猫娘...

题目大意：有 n 只猫，每只猫要吃 m 单位的粮，有 n 包优质猫粮，n 包普通猫粮，优质猫粮打开后会随机来一只没吃饱的猫把它吃完，普通猫粮只有被放在猫猫面前才会被吃，保证所有猫粮加起来一共是 n\cdot m 个单位，一包猫粮装有 [1,m-1] 的粮，问是否有方案使得每只猫猫都一定能吃饱，数据范围 10^5。

观察到每只猫能且只能吃两包粮，因为没有粮能让猫猫一次性吃饱，如果有猫猫多吃了粮就一定有其他的猫猫吃不满两包。

接下来给优质猫粮和普通猫粮分别开桶，将 i 和 m-i 配对即可，注意到优质猫粮+优质猫粮的组合能且只能出现一次，不然就有可能让猫猫没有吃到我们想让它吃到的猫粮，但是有一种特殊情况，当猫粮里装的是 \frac{m}{2} 单位粮时就不怕吃错，特判一下就可以了。

[WC2025 Nim 游戏]()

刚开始还以为是博弈论，结果和这根本就没啥关系。

题目大意：给定 n，m，有 n 堆石子，求最少添加多少堆石子使得每堆石子数异或和为 0，输出 \min(m,方案数) 种方案，数据范围 10^5，石子数正确但方案不正确可得 50\% 分数；特殊性质 A：石子数为 2 的幂次；特殊性质 B：第一堆石子数为 0。

写了个贪心，设现在的异或和为 sum，最高二进制位为 pos，寻找 pos 位为 0 的石子堆，然后将 pos 位搞为 0，若没有则去找 pos+1 位为 0 的，此时一定存在，因为若 pos 位全为 1 则共奇数堆石子，此时要为 0，就一定有 0，然后将 pos+1 位为 0 的这一堆 pos+1 位搞成 1；对于第二种情况 pos 增加后，被增加的堆后面一定都是 0 所以后面在这些位就不会再进行操作二，而操作一 pos 一定减小，所以时间复杂度 O(n \log V)。

最后 pretest 把特殊性质 B 的 50\% 跑了，特殊性质 A 和 n=2 跑满了，最后 50pts，因为 25 个点只有 4 个没特殊性质。

[WC2025 士兵]()

题目大意：给定 n，m，有 n 个士兵，你可以进行若干次操作，每次操作代价 m，可以将一个区间的士兵血量减少 1，操作完毕后若士兵 i 的血量低于 0，可以获得 b_i 点收益，士兵 i 的初始血量为 a_i，数据范围 n\leq 5\cdot 10^5，a_i，b_i\in [-10^9,10^9]。

先将所有的 a_i 和 a_i-1 放一起离散化，应为所有士兵的被操作次数只能是这些，定义 dp_{i,j} 表示枚举到 i，该位进行了 rk_j 次操作的最大收益，rk 为离散化数组，则转移为

前者显然可以后缀最大值优化，后者显然可以单调性优化，考场上就想到这里 40pts，出来告诉我还可以线段树优化，但我暂时还没搞出来，搞出来再说。

Day 3 晚上 WC讲评+文艺汇演

[WC讲评]()

神秘讲题人 3min 速通集训队无人通过 T2 的讲评，并 2min 速通 T3 讲评...

[文艺汇演]()

晚上文艺汇演非常强啊，首先 WA90《春风十里》唱得很好；接着是 Aleph_Drawer 歌曲《Running In The Dark》和 DaydreamWarrior 笛子《深海少女》；然后《信竞大佬》相声挺牛逼的；后面的节目 Meatherm《君色に染まる》，MatrixGroup《命に嫌われている》也都唱得很好；接着炸场的来了：cfz 演讲的《RE：从零开始的异世界OI 生活》，末尾放了个原神？；在他后面 Graygoo 唱了个《啊，朋友再见》，这歌真的适合吗？；中场前最后一首 youdu 的《冬の花》给我唱燃了，好听的欸；

中场休息ing..

StayAlone《花开忘忧》的音色很好欸；边哥的家长《诀别诗》，251Sec / Otomachi_Una / lichenghan / sszcdjrqwq《さくら》，青白《锦鲤抄》，并或集《忘れられないの》，小木虫《老男孩》，wosile 的钢琴《City of Tears》，zhouyuhang & 见泷原中学校 晓美焰《魔法少女小圆》金曲串烧，不会唱歌《最初日》，ningago《白鸟过河滩》，assgin3-32《蜂鸟》，完了都好好听怎么办。

Day 3 晚上 狼人杀混战

[第一把 6 人双身份标准]()

3 号位金宝宝，无队友，白天起来 5 倒一张预验的 1 好人，然后，6 跳守卫，接着 1 4 跳金宝宝，然后我蒙了，不会狼女巫吧，我要是跳是不是就拍刀了？结果 2 拍了个下女巫，那我就稍微放心点了，把金宝宝拍出来对跳了，然后选择了出 3 验女巫，起来 6 单倒 2 自爆，白天起来 1 6 双倒，然后我又蒙了，什么玩意？

这时我的心理：不对啊，1 4 不能双狼啊，狼都爆了一个了；然后我就直接喊话 1 4 让脱身份了，结果 1 脱了说自己是为了保金宝宝，因为 5 6 跳了两张神出来，然后大家就开始盘狼女巫在哪里，最后他们得出结论只有我能拿起，因为 2 跳女巫没人对跳，6 只拍了守卫，4 因为奇妙原因被认下，然后我被投了，起来游戏结束。

最后复盘结果 6 守卫女巫没和 2 对跳？？？那盘个毛线啊。

[第二把 6 人双身份标准]()

依然 3 号位，女巫小狼选女巫在上第一天还救人，哎呀我真棒，起来拍女巫，5 拍了金宝宝，最后投票 6 认出，就投了 6，晚上这个时候如果我毒 5，直接拍两刀理论上就赢了，但是我没有，干了些神奇的事情，就不阐述了。

[第三把 6 人双身份标准]()

法官，第一晚 1 守卫守 6，结果因为狼女巫自己被刀没了，白天 3 5 对跳预言家，5 拍下女巫，然后选择出 5 守 1 闷 3，因为 1 没有拍身份，所以白天起来 1 3 双倒，大家拍身份发现狼必赢，遂交牌结束各回各家。

Day 4 上午 随机性与算法设计——孙晓明

[生日悖论]()

经典概率问题，在场不知道多少人，叫了 3 个人就有会场生日相同的，还算好吧...

For i=1 to 10：随机选取 a_i \in [2,n)\ \cup \ \mathbb{Z}，if a_i^{\frac{p-1}{2}}\neq \pm 1\pmod{n}，或 \forall a_i^{\frac{p-1}{2}}\equiv 1\pmod{n}，输出 No，否则输出 Yes。

算法正确性：error=Pr(a_i^{\frac{p-1}{2}}\equiv 1 \pmod{n})=(\frac{1}{2})^{10}=\frac{1}{1024}。

Day 4 下午 动态图连通性——黄洛天

前置知识：Splay，LCT，ET_Tree，ST_Tree，一个不会，而且看了看讲义应该不是我能听懂的，遂略过。

Day 4 狼人杀混战

看前四把就行了，重点看第四把，因为自己天秀：两晚自刀狼没救+毒死狼王，后四把没啥技术含量，自己写得也很潦草...

[第一把 12 人预女猎白]()

10 号位预言家，第一晚验 8 金水，白天起来警上 2 7 8 10 12，7 号直接退水，8 号给 12 号发杀，我想着不然就让我金水跳呗，遂给 9 号发杀诈身份，后置位 2 号给我发金水，发现我没退水遂称自己滴滴代跳失败，最后其余人全员退水，单边预获得警徽。

警下女巫没救， 8 倒牌报平民，发言 9 划水，5 拍闭眼神，遂认为身份诈对归票 9，晚上验 12 查杀，心里笑开了花：预言家第二天不死，并弄走两头狼，这不天胡吗？

白天起来我倒牌了？？？警徽给 5，因为报了神牌，然后 GrayGoo 告诉我 9 是双药女巫？？？不是女巫接杀不拍身份的？？？

接下来 12 自爆，晚上刀 1，白天 2 5 对跳白痴，后 2 自爆，晚上刀 5 警徽给了 11，白天生推把 6 猎人归出去了？？？

最后复盘，9 女巫被大锅，首夜不救人，接杀还划水，自己背个小锅第一天归了 9；总结：天胡变天崩，双眼泪悠悠。

[第二把 12 人机械狼通灵师]()

3 号位通灵师，晚上验 5 守卫，白天 1 6 7 9 警下，警上 5 说自己有身份，8 通灵给 2 发杀，10 跳女巫没救 8，12 拍民，2 通灵给 5 发猎人，我不敢跳了，跳了不神裸打了吗？遂没跳。警下 8 死开枪带 5？？？接着 2 脱衣服，投了个谁忘了，晚上验 11 狼，白天递话女巫把 11 闷了，然后 2 又把衣服穿上了，那我咋玩啊，只能赌 2 平民了，验 4 平民，白天投完票拍刀了，没办法。

[第三把 12 人机械狼通灵师]()

3 号位平民牌，警上 12 通灵发 8 女巫，10 通灵发 8 平民，10 拿了警徽，警下 8 拍枪，从我开始直接点出来 8 女巫，并认为 8 的这个操作无意义，后面就又把 10 警徽撕了，晚上起来 2 12 双倒，开始盘机械女巫，在我的视角盘 12 是机械毒走的，因为守卫在无解药情况下不可能不受通灵，接着就没看懂 2 为啥死了（后来复盘时告诉我是 8 毒的？？？），白天 4 6 焦点位出了 6，晚上枪倒牌带了 4，9 拍守卫遂跟守卫投票，最后狼人获胜。

复盘结果：6 守卫被枪带走了，和上把守卫一样被枪走的，那 9 穿的身份就没法盘的，这把好人认得下输。

[第四把 12 人狼王守卫]()

3 号位女巫，第一晚 8 倒牌，因为是 GrayGoo，所以没救，第二天窝警下，警上 8 预 10 金水 警徽 3 2，10 预 7 金水 警徽 8 6，11 预 12 查杀 警徽 1 10，12 发言，11 退水，2 预 4 查杀 警徽没留，退水，4 预 12 查杀，退水，5 踩 6 1 8 12，投票 6 弃 1 3 9 投 10，woc 警上发生什么了？？？

警下 8 倒牌，遗言说自己实际验的 2 金水，想诈 10 身份，所以警上才那么发的牌。

放逐发言 2 想打平衡出警徽，我觉得有道理就同意了，最后 2 被出了开枪带 10，警徽飞 7，然后我就铁认 2 真猎人打了接下来的局。

晚上看到 12 倒牌，我想着 12 是个新手，如果她是守卫肯定自守，是民走了也没关系，所以没救，对，我两天没开药。

白天起来 12 单死，1 跳猎人，我没跳，最后 7 归 3 9 PK，我灵机一动，票了 7，5 给 9 上了一票，然后我拍双药女巫强制打平安日让守卫守我，结果 1 给我上了一票，但是 5 给 9 上了又一票，以另一种方式平安日。

晚上看见自己倒牌遂闷 1，白天起来 1 单倒，好了我没打错！！！出 7 撕警徽，7 警徽飞我，晚上肯定我倒牌，5 的操作一定是铁好人，遂警徽飞 5。接下来全看守卫了，死了过后他们告诉我 8 12 双自刀，woc 玩这么花吗，问 12 自刀原因，1 告诉我因为 12 是新手，又是第二天，如果被救了没人会盘她是狼，但是他们没想到我没救哈哈哈。所以接下来 1 狼 1 守 3 平民，白天出了个平民，晚上刀了个平民，最后一推守卫拿下胜利。

赛后复盘，他们一致认为我 MVP：两晚自刀狼没救+毒死狼王，随便打错一个地方好人都得输；但我觉得 5 也占很大功，因为没 5 我双药女巫就要被冲死了，拜谢 5 号牌好吧。

[第五把 12 人盗贼丘比特]()

12 号位平民牌，6 7 8 10 警下，4 预 12 金水警徽 9 8，3 踩 2 4 8 11，2 预 11 查杀，11 自爆，第一天平安夜，晚上起来 8 单倒，6 7 划水，6 自爆，又一个晚上 9 10 双倒，游戏结束，好人胜利；

复盘：woc 第一次盗丘只打了 10min，最后是 4 预，9 狼王被 5 女巫毒走，8 白痴和 7 猎人并没干出什么事。

[第六把 12 人盗贼丘比特]()

3 号位平民牌，4 6 12 警下，11 划水，10 预 7 查杀警徽 12 5，9 划水，8 预 10 查杀警徽 5 1，7 预 6 金水警徽 4 2，后面 8 退水，10 力度大，拿下警徽；第一天平安夜，发言结果 7 基本认出？？？遂出 7，10 在 12 建议下改警徽 4 12，第二天 10 倒警徽飞 12，4 自爆，晚上 5 单倒，12 归 8 9 划水位互投 PK，结果 6 挂了 9 狼王一票，游戏结束，好人胜利，6 12 链子。

[第七把 12 人狼美人骑士]()

3 号位骑士牌，4 6 9 10 12 警下，8 预 4 查杀警徽 1 7，7 5 划水，3 预 2 杀警徽 11 7，后置位没人再跳预，遂自己认 8 单边预退水，8 拿下警徽，警下自己不想给狼人采集更多信息，遂扎 4，然后我断剑了？？？你告诉我单边预还有假查杀的？？？后面好人崩盘，狼人赢，11 背锅警上首置位预言家不跳。

[第八把 12 人狼美人骑士]()

3 号位平民牌，10 12 警下，4 预 8 金水警徽 10 3，8 预 9 查杀警徽 12 6，7 预 10 金水警徽 2 9，后面 7 退水过后还想站起来？？？8 反水立警当选警长，警下 4 拍民，6 拍自证身份神，8 警徽流改 4 2，归票 9，9 狼美带走我 3 号，晚上 2 倒牌，白天出 7，第三晚 8 10 双倒，6 女巫报 2 银水，毒 8，12 扎 11，11 死天黑，白天出 1，游戏结束，好人胜利。

Day 5 上午 稀疏图上更快的单源最短路（SSSP）算法

肚子痛到晚了，呜呜...

Dijkstra：边权 \mathbb{R}_{\geq 0} 的情况，用斐波那契堆可以做到 O(m+n\log n)，最常用。

我们只保证一些点取出来的一些顺序，假设关键点集合为 R \subseteq V，我们试图将每个点挂到距离它最近的关键点上。

记号：b(u) 表示离 u 最近的关键点，Bundle(u) 表示挂到 u 上的点集，Ball(u) 表示离 u 比 b(u) 更近的点集。

需要：构造好这个结构+把 Ball() 中的距离提前计算好。

方法：对每个点做一个局部的 Dijkstra。

具体地，对于 Ball(u) 按照 Dijkstra 的方法，令 S_u 初始为 \{u\}，当 S_u 还有点时，取出其中 dist 最小的节点 v，如果 v\in R 就停下，然后更新它连接的所有其他节点的 dist，并把没访问的放进 S_u，中途碰到的所有其他点放进 Ball(u)。

复杂度保证：将每个点以 \frac{1}{k} 的概率独立随机放入 R，此时 R 的期望大小为 \frac{n}{k} 左右，Ball(u) 的期望大小为 k，建立单个 Ball(u) 的过程为 O(k\log k) 吗？

处理过的点的上界是 Ball(u) 中的点度数之和，所以此时复杂度显然不能保证。

解决办法：将原图转化为常度数图。

具体地，对于点 u 假设其度数为 d_u，在新图中对应以可拥有 d_u 个点的环，环上边权均为零，原图中每条边在每个端点的环上找一个没被其他边用过的点连起来，现在所有点的度数都小于等于 3，但是代价是点数变为了 m 量级，但建单个 Ball(u) 的复杂度得到了保证，总复杂度变为 O(\frac{m \log n}{k})。

更新的大致思路：我们需要它算对两个事情，第一是在取出 R 中的一个关键点是它的 dist 已经算对，还有就是往后更新前，Bundle 里的点所有 dist 也要算对。

对于第一件事，考虑最短路径上最后一个完成的 Bundle，它的下一个点一定是当前 Bundle 中的点，所以只需要每次向后更新 Bundle 中的点的邻居和它们挂到的关键点即可。

对于第二件事，考虑最短路径上最后一个完成的 Bundle，比较其下一个点所在 Bundle 对应的路径，用当前点是堆中最小点的性质，此时两个 Ball 在路径上一定有交（这个东西因为走神了，没完全弄懂...）。