题目列表

把两只青蛙第 t 次跳跃后位置相等写成 (m-n)t≡y-x(mod L)，再用扩展欧几里得求最小非负解；若 gcd(m-n,L) 不能整除 y-x，则无解。

把 ax≡1(mod b) 改写成 ax+by=1，用扩展欧几里得求出一组解，其中 x 在模 b 意义下的最小正值就是答案。

设 f[i] 表示杀死一只 i 号怪兽的最小体力，满足 f[i]=min(K_i, S_i+Σf[spawn])。先把法术攻击代价当作初值，再从已确定更小代价的子怪兽反向更新父怪兽。

对每个城市分别维护“机器人最早能到城门的时间”和“所有前置发生器最晚被摧毁的时间”，城市真正被摧毁的时间是这两者的最大值，再用 Dijkstra 式过程按时间推进。

把状态定义成“当前所在牧场 + 已改造道路数”。走一条边时要么正常付边权，要么消耗一次改造机会把这条边代价降成 0，在状态图上跑 Dijkstra。

把状态定义成"当前所在城市 + 已用卡数"。走一条边时要么正常通过，要么额外消耗一张卡把这条边代价减半，在这个状态图上跑 Dijkstra。

把每个关键交点拆成“横线状态”和“竖线状态”两个点；同一条线上的相邻关键点连边，换乘站内部连一条代价为 1 的边，再在这张图上跑最短路。

按牧场过路费从小到大加入 Floyd 中转点，维护边权和最短路；每次加入新中转点后，用“边权和 + 当前允许最大点权”更新所有点对答案。

先求出一条 1 到 N 的最短路。只有这条路上的边被封闭才可能让答案变大，因此依次禁用这些边并重跑最短路取最大值。

把已有电线当成 0 权边，把距离不超过 M 的点对当成可补的新边，在这张图上跑最短路求从 1 到 N 的最小补线长度。

先 Floyd 求每个连通块内任意两点最短路，再枚举跨块连边，用两端点到各自块内最远点的距离更新合并后的最小直径。

先求出一条从 1 到 N 的最短路。只有这条路上的边加倍后才可能让答案变大，因此枚举这条路上的每条边临时加倍，再重跑 Dijkstra 取最短路增量最大值。

只需要比较两种送货顺序：PB->PA1->PA2 和 PB->PA2->PA1。图是无向图，因此求出 PB 到两点的距离和 PA1 到 PA2 的距离后即可直接取最小值。

所有奶牛都要判断能否在 M 秒内到达同一个目标点 1，所以只需从 1 号草地做一次 Dijkstra，再按奶牛编号检查距离是否不超过 M。

这是无权图单源最短路。先从 1 号点做 BFS，得到每个点的最短层数，再统计最远距离、最小编号和该距离出现次数。

这题不是最短路求和，而是最小化路径上的最大边权；点数只有 300，可以直接用 Floyd 的 min-max 转移求所有点对的最小瓶颈路。

牧场总数只有 52 个，把大小写字母映射成编号后直接 Floyd 求全源最短路，再在 A..Y 中找离 Z 最近的那头牛。

往返距离等于 i 到 x 再加 x 到 i；原图从 x 跑一次 Dijkstra，反图再从 x 跑一次 Dijkstra，就能得到所有点的来回最短路。

标准正权无向图单源最短路，直接从起点 s 跑一次 Dijkstra，输出到终点 t 的距离即可。

路线被强制经过 1 号牧场，所以先从 1 号点跑一次 Dijkstra，任意询问答案都是 dist[p] + dist[q]。

利用无向图距离对称性，从每个喜欢的牧场各跑一次 Dijkstra，把到所有点的距离累加后取总和最小的牧场。

路径加可以先做树上差分，再把子树和展开成 diff 的加权求和；结合 LCA、DFS 序和两棵树状数组，就能在线维护路径加与子树和查询。

两点间最优通信稳定性等于所有路径中最小边权的最大值，这正是最大生成森林上的路径最小边权；先 Kruskal 建最大生成森林，再用倍增 LCA 查询路径最小边。

对每个节点预处理根到它路径上的 depth^k 前缀和，再用 LCA 把路径拆成两段：sum(x)+sum(y)-2sum(lca)+depth(lca)^k。

商人的总路程就是从首都出发后，相邻两站之间树上距离的总和；用倍增 LCA 快速求两点距离，再顺着给定路线累加即可。

把每台电脑的度数看成点权，询问就是树上两点路径点权和；预处理根到每个点的前缀和，再用 LCA 把路径拆成两段即可。

一组员工都能被同一人管理，等价于这个人是他们的公共祖先；先求这组点的 LCA，再在根到该 LCA 的路径上取最大编号即可。

封锁一个点后，真正新增损失来自它把图切成的多个连通块；用 Tarjan 求割点时顺手统计每个被切下来的子树大小，就能在线性时间算出每个点造成的访问损失。

把每个兴奋值看成一个状态值，若某个兴奋值 x 能选择一个结束兴奋值为 y 的游戏，就连边 x->y；某个游戏能玩两次，当且仅当它的 e_i 能回到某个整除 w_i 的同 SCC 状态。

关键线路一定是桥；先用 Tarjan 找桥，再统计桥两侧是否都同时含有 A、B 两种服务，只要某一侧缺少其中一种服务，这条桥就是答案。

先把同高且连通的格子缩成强连通块，块间只能从高处指向低处，缩点后是一张 DAG，最少缆车数就是入度为 0 的块数与出度为 0 的块数的较大值。

Tarjan 回溯时若树边 u-v 满足 low[v] >= dfn[u]，说明 v 子树必须经过 u 才能连到外部，此时把点栈弹到 v 再加上 u，就得到一个点双连通分量。

在无向图上跑一遍 Tarjan，若某个儿子 v 满足 low[v] >= dfn[u]，就说明删掉 u 会让这棵子树断开；根节点还要单独判断子树个数。

先用 Tarjan 找出无向图中的所有桥，再把这些桥删掉，剩下的每个连通块就是一个边双连通分量。

把无向图做一遍 Tarjan，若树边 u-v 满足 low[v] > dfn[u]，说明 v 子树回不到 u 及其祖先，这条边就是桥。

先求从 1 号景点出发能到达的全部景点；在这些点上按边的较低端高度降序、边长升序做 Kruskal，可以在保证可达景点数最大的前提下，把总滑行距离压到最小。

二分最大允许造价 T。对每个 T，只看二级造价不超过 T 的边是否能连通全图，再看一级造价不超过 T 的边最多能提供多少条一级公路，从而判断可行性。

每周只新增一条边，因此当前最小生成树只可能通过“接上一条新边”或“用新边替换环上的更大边”发生变化；维护最小生成森林即可在线输出答案。

先用 BFS 求出任意两座城市之间的最短骑士步数，再把“从已占领城市攻占一座新城市”的代价视作边权，整道题就转化成一棵最小生成树。

题面按轮修路的过程本质是在构造欧几里得最小生成树，最终总长度就等于 MST 边长之和；点数较大时直接用 Prim 求解即可。

这是带门槛的最小生成树：只有距离平方不小于 c 的边允许使用，直接在完全图上做 Prim，若中途出现不可达点则答案不存在。

要求把 N 个点连成恰好 K 个连通块且总代价最小，本质就是最小生成森林；按边权从小到大做 Kruskal，连到只剩 K 个连通块时停止。

把“原价买一件礼物”看成从虚拟源点连一条权值 A 的边，把优惠价看成礼物之间的边权，原题就转化成一棵最小生成树。

要求先用最少的边把全图连通，因此一定选 n-1 条边；再把这些边中的最大权值压到最小，直接按边权从小到大做 Kruskal，最后一条加入的边权就是答案。

把两棵树之间能否跳过去看成边，所有树都能互达所需的最小跳距，等于一棵最小生成树中的最大边长；用 Prim 求出这个临界值后统计能达到的猴子数量。

在保留成树的前提下，一条边必走两次，而点 i 的谈话时间会按它在树中的度数计入；把每条边改写成 2*l+c_u+c_v，再额外加上最小的起点费用即可。

因为边权是严格递增的 2^i，最优环一定在按边编号从小到大加边时第一次形成；先用并查集找到这条边，再在此前形成的森林里找两端唯一简单路径。

题目给的是完整邻接矩阵，直接用 Prim 维护每个未选点到当前生成树的最小连边代价，逐个把点加入生成树即可。

把每次有效连边变成并查集合并树上的一个新父节点，测试操作只给当前连通块根打标记，最后 DFS 一次把信息总量下传到所有原节点。

并查集合并已有道路并实时维护连通块数，最少新道路数就是连通块数减一。

把每一列看成一个并查集集合，维护每艘战舰到队头的距离；合并时整体挂到另一列后面，就能在线回答两舰之间隔了多少艘船。

把每个数出现后占掉这个位置，并查集维护“从某个值开始往后第一个没被占用的位置”，从而快速找到修改后的最小可行值。

用并查集维护若干元素所属的集合，操作 1 合并两个集合，操作 2 判断两个元素是否已经连通。

分别求出 A 公司里与 1 号同组的人数、B 公司里与 -1 号同组的人数，答案就是这两个连通块大小的较小值。

把关闭谷仓的过程倒过来看成重新开门，按倒序激活点并用并查集维护当前开着的连通块数量。

把每个格子看成一个点，出现连根关系就并查集合并两个编号，最后连通块数量就是合根植物的总株数。

先判定有向欧拉路存在条件，再把每个点的出边按升序走 Hierholzer，最后逆序得到字典序最小的欧拉路径。

把限制反向建图，用大根堆在反图上做拓扑排序，再把得到的序列倒过来输出，就能得到题目要求的最优顺序。

把函数调用关系看成 DAG，先反向求每个函数整体乘法效果，再正向统计每个加法函数最终会被乘上的系数。

在 DAG 上同时维护从起点到每个点的路径条数和所有路径长度总和，最后加上每次重新坐船返回的固定时间。