暴力连边肯定不行。有没有什么东西是把一个区间拆分成 log⁡log 个的当然是线段树优化建图啦。因为加入的是一个区间所以用线段树上的 log⁡log 个结点来表示区间对这些结点连边。对于 [l,r]→v[l,r]→v把 log⁡log 个结点连向线段树上的 vv之后把线段树本身连成一颗内向树。对于 [l,r]←v[l,r]←v在对线段树内部连边时显然不能和上一种情况连同一些结点不然最短路都是 00。于是重新开一颗线段树把这个颗树连成外向树。对于这颗线段树上的 log⁡log 个结点连向上内向树上的 vv。这两颗树上的叶子在原图上是同一个点所以这两颗树的叶子要连权值为 00 的边显然只需要外向树向内向树连边。对于建出来的图跑最短路有 nn 个结点 mlog⁡nmlogn 条边堆优化 Dijkstra 时间复杂度 O(mlog⁡2n)O(mlog2​n)。CF786BII. 后缀树P5284 [十二省联考 2019] 字符串问题用后缀树优化建图然后跑 DAG 上 DP。P5284III.倍增 or ST表 虚点P5344 【XR-1】逛森林解法 11区间向区间连边转化为区间向虚点连边虚点向区间连边。倍增优化建图与线段树类似只不过放到了树上。需要建出两个倍增树一个管理出边一个管理入边。时间复杂度为 O(mlog⁡nlog⁡(mlog⁡n))O(mlognlog(mlogn))。解法 22可以将树通过 dfs 序拍到序列上并使用 ST 表维护连边。具体地可以将 [l,r][l,r] 拆成 [l,l2k)[l,l2k) 和 (r−2k,r](r−2k,r]其中 kk 为 ⌊log⁡2(r−l1)⌋⌊log2​(r−l1)⌋因为重复连边不影响最终的答案。时间复杂度 O(mlog⁡m)O(mlogm)。P5344IV.线段树 虚点P1983 [NOIP 2013 普及组] 车站分级解法 11暴力对于一条线路 t1→t2→⋯→tst1​→t2​→⋯→ts​将所有编号在该线路之间却没有经过的站点 p(∈[t1,ts]p(∈[t1​,ts​] 且 p∋tip∋ti​ 向所有经过的站点 titi​ 连一条边 p→tip→ti​ 表示 pp 的编号一定小于 titi​然后跑拓扑排序即可。一次连边 O(n2)O(n2)总时间 O(n2m)O(n2m)。解法 22虚点根据例题 III. 可知区间向区间连边可以用虚点优化。需要注意最终答案要除以 22因为点到虚点再到点的长度为 22而实际上应该为 11。时间复杂度 O(nm)O(nm)。P1983解法 33线段树 虚点点与区间的连边用线段树优化即可。最后跑拓扑也在线段树上跑。时间复杂度 O(mlog⁡n)O(mlogn)。最短路建模P9351 迷宫 / Maze题目描述考虑把打通的代价和变化表示出来那么就是选择打通就要 11 的代价然后可以走 n×nn×n 的 00 权边。但是给每个点新建一个 n×nn×n 的 00 权图复杂度太大能不能只建立一个辅助图同时在这个图上限制只能走 n×nn×n。如果将一个正方形打通则可以再上面不管障碍物地乱走然后在某个地方走出去。所以有三种情况不管障碍物、管障碍物、随便走不管障碍物。所以考虑建立两个图第一个图是原图上面的.都可以走。第二个图描述 n×nn×n 的覆盖八联通边权都为 11限制一次走的边权小于 nn。然后第一个图的点可以四联通的走到第二个图上代价为11。那么相当于双关键字最短路两张图也没必要真的建出来第二个关键字跑满再走第一个关键字这样就能01bfs了。P9351ARC084B题目描述直接做倍数之类的不太好做。注意到 KK 很小可以考虑 modK0modK0 就是 KK 的倍数从 modKmodK下手。考虑从 11 开始通过 ×10×10 和 11 同时不进位凑一个 KK 的倍数这一定可以做到。×10×10 对数位和的贡献为 0,10,1 的贡献为 11判断是否为倍数只需要考虑 modKmodK 是否为 00。建立一个图不需要真的建x→0x×10modKx0​x×10modKx→1(x1)modKx1​(x1)modK跑01bfs求出最短路即为答案。ARC084BP7297 [USACO21JAN] Telephone G题目描述需要刻画哪些奶牛能交流。先把绝对值拆开然后真的需要每个奶牛都连边吗直接建图是 O(n2)O(n2) 的注意到 kk 很小。对每种奶牛建立一张新图每张图内部按照位置排序相邻的奶牛之间连边。同时保留一张原图原图是 nn 只奶牛之间不连边。对于一只奶牛 xx枚举它能走到的哪种奶牛找到位置小于它的最大的和大于的最小的该种奶牛 y1,y2y1​,y2​连接 xx 原图和 y1,y2y1​,y2​ 新图。不难证明任意两只能互达的奶牛 i,ji,j 之间的最短路等于 ∣i−j∣∣i−j∣。图的点数为 O(n)O(n)边数为 O(nk)O(nk)跑 Dijkstra 即可。P7297P4366 [Code#4] 最短路题目描述异或的每一位是独立的可以拆开考虑把异或边权拆开ii 向 i⊕2ji⊕2j 连边权 2j×C2j×C 的边i⊕2j≤ni⊕2j≤n。然后直接对这 nlog⁡nmnlognm 条边跑最短路即可。P4366AT_abc164_E Two Currencies题目描述发现 1≤n≤501≤n≤50 非常奇怪。设 di,jdi,j​ 为在点 ii 有 jj 个银币的最短路由于 ∑i1nxi≤49×50i1∑n​xi≤49×50所以 j≤2450j≤2450如果超过了 24502450 也看作 24502450 因为已经足够了。然后在 di,jdi,j​ 之间连边也就是跑分层图最短路也是非常巧的。AT_abc164_E*P9370 [APIO2023] 赛博乐园 / cyberland好题建议看一下题目。给定一张 nn 个点 mm 条边的无向图经过第 ii 条边会用 wiwi​ 的时间。有些点在经过时可以选择改变总通过时间多次经过可以多次改变但是除以 22 只能使用 kk 次。arri0arri​0经过这个点会使得总通过时间为 00。arri1arri​1不改变总通过时间。arri2arri​2经过这个点会使得总通过时间为 总时间22总时间​。保证 arr0arrH1arr0​arrH​1求 0→H0→H 的最短通过时间。交互多组询问2≤n,∑i1nn≤105,0≤m≤min⁡(105,n(n−1)2),∑i1nm≤105,1≤k≤106,1≤ci≤1092≤n,i1∑n​n≤105,0≤m≤min(105,2n(n−1)​),i1∑n​m≤105,1≤k≤106,1≤ci​≤109。答案会是浮点数所求答案与正确答案误差在 1−61−6 内即可且有 K≤30K≤30 的部分分。首先把图反着跑这样总通行时间除以 22 就变成了后续时间都除以 22当前总通过时间为 00 就变成了后续时间都为 00。KK 很小考虑用分层图来做然后把一个点拆开成 K2K2 个第 ii 个代表经过 ii 次除以二操作的点最后一个代表经过清零操作的点然后跑最短路。注意一下 HH 不能多次经过和不能达到为 −1−1这样就有 9797 分了。仔细想了一下发现和 P4145 这题一样的思路可以说一样。P4145 是给一个区间开方显然用线段树但是一个小于 109109 的数开 55 次方就已经是 11 了没有必要再开方了。而这道题除以二的操作做 log⁡2105×10910−6≈70log2​10−6105×109​≈70 次就会变成可忽略值所以 KK 和 7070 取最小的那一个就行。P9370P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus题目描述求出最短路树枚举翻转那条边。如果翻转的是树边重新跑最短路树边只有 O(n)O(n) 条。如果翻转的是非树边 x→yx→y最短路变为min⁡(dis1,n,dis1,ywx,ydisx,n)min(disn,1,disn,ywx,ydisx,1)min(dis1,n​,dis1,y​wx,y​disx,n​)min(disn,1​,disn,y​wx,y​disx,1​)。证明显然不存在经过 x→yx→y 翻转后的更短的路径。P6880P9724 [EC Final 2022] Chase Game题目描述如果瞬移了一次那么以后的伤害都是 d,d−1,…,1,dd,d−1,…,1,d顺移到的都是之前走过的位置如果距离没变那么距离终点的最短路也没变白吃了伤害。剩下的就是最开始距离小于 dd 的位置对这些位置跑最短路。之后直接走到终点的最短路此时已经瞬移了一次了。P9724P5905 【模板】全源最短路Johnson题目描述我们考虑使用 Dijkstra 来解决但是 Dijkstra 不能处理有负权的图考虑通过一些方法把图变为非负权图再跑 nn 次 Dijkstra。新建一个虚点向所有点连一条长度为 00 的边求出这个点到所有点的单源最短路。设虚点到 uu 的最短路为 huhu​ 对于一条 x→yx→y 的边权为 ww 的边边权改为 whx−hywhx​−hy​ 。接下来跑 nn 次 Dijkstra 即可。时间复杂度瓶颈在于 DijkstraO(nmlog⁡m)O(nmlogm)。从 ss 点到 tt 点的一条路径 s→p1→p2→⋯→pn→ts→p1​→p2​→⋯→pn​→t 的最短路(ws,p1hs−hp1)(wp1,p2hp1−hp2)⋯(wpn,thpn−ht)ws,p1wp1,p2⋯wpn,ths−ht(ws,p1​​hs​−hp1​​)(wp1​,p2​​hp1​​−hp2​​)⋯(wpn​,t​hpn​​−ht​)ws,p1​​wp1​,p2​​⋯wpn​,t​hs​−ht​那么对于新图上 s→ts→t 的长度为 ww 的最短路真实的长度为 w−hshtw−hs​ht​。而原图上任意一边 x→yx→y 满足 hy≤hxwx,yhy​≤hx​wx,y​所以 wx,yhx−hy≥0wx,y​hx​−hy​≥0。P5905P3403 跳楼机题目描述钦定 xyzxyz令 didi​ 为只通过 y,zy,z 能到达的满足 modximodxi 的最低楼层考虑同余最短路建图i→y(iy)modxiy​(iy)modxi→z(iz)modxiz​(iz)modx跑最短路即可然后不停地走 xx所以答案为∑⌊h−di−1x⌋1∑⌊xh−di​−1​⌋1CF986F Oppa Funcan Style Remastered题目描述改为质因数显然等价。当 ≤2≤2 个质因数时是平凡的特判和 exgcd 即可。22 个时最小的质因数 ≤105≤105和 P3403 类似建立同余最短路模型。CF986F*CF1163F Indecisive Taxi Fee题目描述我们发现怎样转化取决于修改的是否是 1→n1→n 的最短路上的边所以有以下分讨如果过修改的不是最短路上的边 x→yx→y答案为 min⁡(disi,n,dis1,xtdisy,n)min(disi,n​,dis1,x​tdisy,n​)。如果修改的是最短路上的边若边权变小则答案为 min⁡(dis1,n,dis1,xtdisy,n)min(dis1,n​,dis1,x​tdisy,n​)若变大则是删掉这条边后 1→n1→n 的最短路与 dis1,xtdisy,ndis1,x​tdisy,n​取 min⁡min。易知有以下结论结论 111→x1→x 的最短路必定存在一条与 1→n1→n 共享且仅共享一条前缀。通过最短路树易证。结论 22删掉第 ii 条边后的最短路和 1→n1→n 的最短路共享一个前缀和后缀。由于是无向图1→n1→n 的最短路也是 n→1n→1 的最短路根据结论 11 易证。结论 33中间这段腾空的弧里有且只有一条非最短路树边。根据最短路树易证不会删了一条换两条进来。所以枚举非最短路边 x→yx→y从 x,yx,y 分别走若干条树边到达 1→n1→n 最短路上的两个点 l,rl,r贡献区间为 [l,r][l,r]贡献值为 dis(1,x)wx,ydis(y,n)dis(1,x)wx,y​dis(y,n)。线段树、或者离线差分 multiset 即可。CF1163FP2483 【模板】k 短路 / [SDOI2010] 魔法猪学院题目描述建立以 tt 为根的最短路树 TT。性质 11令 P′P−(P⋂T),PP′P−(P⋂T),P 为 s→ts→t 的边集。对于 P′P′ 中相邻的两条边 e,fe,fss 到 tt 顺序满足 ff 的起点为 ee 的终点在 TT 上的祖先或自己。性质 22lengthpdiss,t∑e∈p′,e(u→v)disvw−disulengthp​diss,t​e∈p′,e(u→v)∑​disv​w−disu​令 ∑e∈p′,e(u→v)disvw−disuw−disue∈p′,e(u→v)∑​disv​w−disu​w−disu​ 为 Δp′Δp′问题转化为 ΔΔ 第 kk 小的 P′P′。用小根堆维护 P′P′每次取出最小的当前 P′P′ 的 P(s→t)P(s→t)替换 tt 为起点的边为一条最小的大于它的非最短路边。加入一条以 tt 为起点的最小的非最短路边 t→xt→xxx 在 TT 上是 tt 的祖先 tt 变为 xx。显然可以按照大小得到所有的 P′P′。使用可持久化合并堆维护祖先除去的所有非最短路边的最下边即可。P2483__EOF__本文作者Nimbunny本文链接各种优化建图、最短路建模技巧 - 酱云兔 - 博客园关于博主评论和私信会在第一时间回复。或者直接私信我。版权声明本博客所有文章除特别声明外均采用 BY-NC-SA 许可协议。转载请注明出处声援博主如果您觉得文章对您有帮助可以点击文章右下角【推荐】一下。分类: 学习笔记标签: 图论, A学习笔记免责声明本内容来自平台创作者博客园系信息发布平台仅提供信息存储空间服务。推荐该文 关注博主关注博主 收藏本文 分享微信酱云兔粉丝 - 10 关注 - 17加关注10« 上一篇 图论 II» 下一篇 7.15小测posted 2025-07-14 21:02 酱云兔 阅读(175) 评论(0) 收藏 举报登录后才能查看或发表评论立即 登录 或者 逛逛 博客园首页【推荐】 凌霞 618 年中大促Halo 与 1Panel 产品全线半价叠加满减【推荐】科研领域的连接者艾思科蓝一站式科研学术服务数字化平台编辑推荐在 .NET 上构建超大托管数组[经验分享] 我的第一个 Skill让 Agent 在对话中成长自进化机制的五层实现代码之外一个技术人的职场困境与自我和解贩卖焦虑的时代我终于接住了真实的焦虑各种优化建图、最短路建模技巧25/07/14 21:02175014096381:55 ~ 136:32学习笔记图论A学习笔记This blog has running : 414 d 13 h 57 m 25 s ღゝ◡╹)ノ♡友情链接于沛东/彭刘济湛/陈俊宇/张文宇/待填博客园 © 2004-2026 浙公网安备 33010602011771号 浙ICP备2021040463号-3