2025年9月4日
生成树
摘要： 承接上篇。 无向图最小生成树 简单题目 并非简单。 P1967 考虑求出最大生成树后倍增 LCA 处理树上两点间的最短路径，答案就是这个。 CF888G 类似 Kruskal，我们考虑找尽可能短的边权连接两个连通块。 考虑建一棵 trie 树，从高位到低位加入所有数。对于一个点 \(p\) 的左右子 阅读全文
posted @ 2025-09-04 15:34 はなこくん 阅读(25) 评论(0) 推荐(0)
最短路
摘要： 对于 Alex_Wei 老师的图论内容的学习。 最短路 一些套路 P1462 套路题，考虑二分转判定。只用点权 \(\leq mid\) 的边然后跑最短路即可。 P4568 \(k\) 很小，所以直接记录到最短路状态中即可。其实就是分层图最短路。 CF1765I 会发现 \(y\) 很小，所以斜着走 阅读全文
posted @ 2025-09-04 15:09 はなこくん 阅读(12) 评论(0) 推荐(0)