2024-02-04发表2024-02-04更新学习总结19 分钟读完 (大约2781个字)

拓扑排序

定义

拓扑排序是对其顶点的一种线性排序，使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边 $u \to v$ ，$u$ 在排序中都在 $v$ 之前。运行此算法需要保证图是DAG。

差分约束

说白了，就是给出一个序列内数与数之间的关系，可能是大小关系，也可能是作差的数值，让我们尝试还原整个序列。

首先，这两种问题都得先转化成图上问题来做。

subtask 1：大小关系

考虑建图：设一条有向边 $u \to v$ 表示 $b_u > b_v$。有解时构建出来的图是一个DAG，并且如果在上面跑拓扑是能够确定所有 $b_i$ 之间的大小关系的；无解时，图上会存在一个环。

例题：数列恢复（半模板题），Pustynia（线段树优化）。

subtask 2：作差数值

这种情况需要使用最短路。鸽一会。

输出方案满足“尽量”关系

首先我对于这个方案有一个谁在谁前面有很多个限制。

大致如下：

在满足所有限制的前提下，$1$ 尽量靠前。
在满足所有限制，$1$ 尽量靠前的前提下，$2$ 尽量靠前。
在满足所有限制，$1$ 和 $2$ 尽量靠前的前提下，$3$ 尽量靠前。
在满足所有限制，$1$ 和 $2$ 和 $3$ 号尽量靠前的前提下，$4$ 尽量靠前。
以此类推。

很多人可能认为这就是字典序，其实不然。考虑这组数据：

以及

这里放个结论：最终的序列是满足限制的前提下字典序最大的倒序。

有大佬证明了，在这里贴个链接。

例题：菜肴制作（板）。

二分图的判定

染色。

欧拉路

最灵活的一集。

首先是如何判欧拉通路和欧拉回路以及证明。

Theorem 1 无向连通图中存在欧拉回路当且仅当图中所有顶点的度数为偶数。

充分性：欧拉回路从起点出发对起点产生 $1$ 的度数，而后经过的除终点（也就是起点）外每一个点产生 $2$ 的度数，最后回到起点又对起点产生 $1$ 的度数。

必要性：考虑使用构造法证明。我们每次在图中寻找一条回路，如果这个回路是欧拉回路，那么结论成立；否则删除环上所有的边以及一些孤立点，明显剩下的这个子图的所有点的度数都是偶数但可能不连通，并且这个子图一定和找到的回路有一个公共点，那么再次以这个公共点为起点继续寻找回路并重复以上过程直到找不出来为止。找完后将这些回路串起来就是最终的欧拉回路了。

Theorem 2 连通多重图中存在欧拉通路且不存在欧拉回路当且仅当连通图中有且只有两个顶点的度数为奇数。

证明过程和上面的类似，这里不做阐释。

而如何跑欧拉路，上面证明给出的构造方案已经说得很清楚了。

例题：POLICE（很难看出来这是一道欧拉路的题目），丁香之路（与MST相结合）。

看到图论题不会做就想想能不能欧拉回路。

——0htoAi

最小生成树

最小生成树大多数时候用的是它的一个思路，毕竟人家不太可能把板子明摆着让你写。

有两个算法，但是两个算法的本质都是贪心。

Kruskal

将所有边按边权从小到大排序，再依次加边，并用并查集维护是否会出现环，如果加入一条边后有环则不加。正确性显然。

如果有边是必选的话就可以提前在并查集里加边，后续不用做任何更改。

时间复杂度：$O(m \log m)$

~~谁完全图用这个算法我笑他一辈子。~~

例题：丁香之路（与欧拉回路相结合）

Prim

从一个点开始每次选择与这个点相邻的最短的一条边，加入这条边和对应的点，再找距离这两个点最近的其他点进行添加，以此类推。

时间复杂度：$O(m \log n)$

图的连通性

这个知识点之前写过，这边建议出门左转二分图与图的连通。

例题：未整理。

耳

这个知识点在NKSWC的第【数据删除】场测试中出现了，因此咕一下（什么逻辑）。

并查集

几个小技巧。

删边倒序处理

如果出现删边类型操作的话，可以将询问离线下来倒着处理。

删点=新点

如果删除一个点之后不会出现任何与这个点有关的操作的话，可以记录一个 $id$ 数组，删点就直接弃用之前的点并建立新点。

撤销操作

注意数据范围。建边时记录操作序列，每次回溯直接重置 $fa_i$ ，这意味着并查集将不能路径压缩或按秩合并。

例题：没有。

单调/优先队列

单调队列优化DP

当状态转移是下面这种形式时，可以使用单调队列进行优化。

$$
f_i=\max_{j=l}^r f_j+val(i,j)
$$

即用单调队列维护 $j$ 的值，最终状态从单调队列的队尾转移。

例题：未整理。

带悔贪心

目前我见过的这种类型的题目用一只手都能数过来。

简单而言，就是把选和不选的情况分开考虑，一个直接贪心，另一个放到单调队列里等待后面取出。而一个不选的状态的代价是扣除选的价值再加上不选的价值。总之就是一个字：抽象。

这种题目应该是做多了才能看的出来吧。

例题：数据备份。

线段树

线段树优化建图

用线段树上的点来凑出一个区间。

如果有区间连点和点连区间同时出现的话要建立两棵树，一个负责入，一个负责出。

要考虑好大区间与小区间是否有关系，如果有也需要建边（目前来看都是有的）。

例题：Pustynia（与差分约束结合）。

题目专版

数列恢复

有一个序列 $a$，长度为 $n$，且对于任意一个 $i(1 \leq i \leq n)$ 满足 $|a_i| \leq n$，定义 $s_{i,j} = a_i + a_{i+1} + … + a_j$，现在给定所有 $s_{i,j}(1 \leq i \leq j \leq n)$ 的正负性，输出任意一个合法的 $a$ 序列。

然而这道题给的是每段区间和 $0$ 的大小关系，无法转换到上述模型。因此我们考虑将原式中的 $s_{i,j}$ 转化为前缀和形式：$s_{i,j}=sum_{j}-sum_{i-1}$，这样就能转换了。套用模型，最后能够处理出来每个 $sum_i$ 的大小关系。

有一点细节是当 $s_{i,j}=0$ 时，也就是 $sum_{i-1}=sum_{j}$，跑拓扑更新到这两个点中的任意一个时要同步更新另一个。

Pustynia

给定一个长度为 $n$ 的正整数序列 $a$，每个数都在 $1$ 到 $10^9$ 范围内，告诉你其中 $s$ 个数，并给出 $m$ 条信息，每条信息包含三个数 $l,r,k$ 以及接下来 $k$ 个正整数，表示 $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$ 里这 $k$ 个数中的任意一个都比任意一个剩下的 $r-l+1-k$ 个数大（严格大于，即没有等号）。需要任意构造出一组满足条件的方案，或者判断无解。

这一道题和这道题差不多，都是建图跑差分约束模型，但是此题需要使用线段树优化建图。

菜肴制作

给定 $n$ 个菜肴和 $m$ 条限制条件，对于每个限制条件 $x$ 和 $y$，表示 $x$ 号菜肴必须先于 $y$ 号菜肴。让你求出在满足最小号的菜肴尽量靠前的前提下次小号的菜肴也尽量靠前，次小号的菜肴尽量靠前的前提下次次小号的菜肴也尽量靠前，并以此类推。（注意不是字典序！）以此类推，最优的菜肴制作顺序。如若无解，则输出 Impossible! 。

如题。

POLICE

有一个 $n \times m$ 的矩阵，每个位置上有一个数，现在要将这个矩阵通过两种操作还原成初始状态，保证原矩阵里的数和现在的数一致。

操作1：交换同行两个相邻位置上的数。

操作2：交换任意两个位置上的数。

请求出需要的执行操作2的次数最少是多少，或者输出无解。

先把例题摆着，因为这道题我也没过。

丁香之路

数轴上有 $n$ 个点，表示的数分别是 $1\sim n$，有 $m$ 条连接两个点的边（独立于数轴的），这些边必须走一遍，求 $s$ 到其他点的最短路。

搁置一下。

数据备份

搁置一下。

2024-01-13发表2024-01-13更新学习总结6 分钟读完 (大约970个字)

期末总结

知识总结就不放在这里了，往回走走就能看到的。

这学期的一些问题

论：如何打击自己的自信

平时练习

做题时没法深入思考，也不知道如何提升这方面的能力；思路很跳跃，虽然不排除正好跳到正解的可能性，但是就是没法深入；又感觉自己有点急于求成，高估自己进步的速度了。

而且仔细回想一下，发现整个作业表的题并不是自己推着在走（倒也不是完全都是，不是的很少）而是自己在被拖着走，有的题目没来得及思考就讲评了。在讲评前过的题也有很大部分是和同学讨论过的。说绝对点就叫不会独立思考，再说深入点：懒得思考。

考试时

考试的时候没有策略。有时对着一道题死磕好久然后发现思路从一开始就不正确而白白浪费几个小时，有时对着一道题看了一会有点思路又深入不进去导致最后惊奇地发现自己和正解的思路只有一道红题的距离。即使有了思路，代码实现也是各种粗心的问题都会犯，见区间DP总结T2。感觉代码力也要不行了。。。

而且这里有几个我认为重大的问题：

破题的能力很有问题，比如这次考试的T1，我就认为它是纯纯的基础的有规律的构造，完全没往搜索那个方面想，这也和我在思考是做的数据不够大有关。也许这和我的练习情况有关，就是练少了，见过的题太少，但是就是这样我也没有办法去针对性的练习。

而且思考时很少用纸笔去思考，大部分时间大脑都是在空转。

拿到一道题不知道从哪里下手 ~~，于是干脆不下手~~ 也不会去尝试，妄图一步到位直接AC，忽略了部分分及其的作用。例如有一些看起来不正确的搜索（时间复杂度无法证明/说明）就直接不去写。

“正解”写出来之后也基本不会去对拍或是写个SPJ，最多写个很水很水的hack。最后是所谓的正解只得了60分甚至爆零（区间DP总结T2还是个很好的例子）。

考试时很难有信心，导致出成绩时心态死活调整不过来，形成恶性循环。

讲评时

这学期听MikeZ讲题下来，会在讲题时做一些笔记了，但是讲完后仍然很难从笔记中整理出一条完整的的思路，就是说笔记没法连起来，是散的。这导致什么呢？以后来复习的时候根本看不懂。（笑

发现MikeZ讲题时总会在题目讲完之后想到一些拓展，假如这个问题是个计数问题呢？假如要求字典序最小的方案呢？做题AC的时候多像MikeZ这样问问自己总会有点好处的。

理下来感觉自己一无是处了。

没有几天就是第二次选拔了，希望我能抓紧这最后的几天时间把一些没搞懂的知识再搞懂，大力复习，在即将到来的这一场考试中好好发挥，考出一个理想的成绩！ヾ(≧▽≦*)o

2024-01-06发表2024-01-09更新学习总结 / 考试几秒读完 (大约36个字)

0106考试总结

标签：随机化根号分治

随机两个数作差，枚举这个数的因数作为可能的答案验证。

2024-01-02发表2024-01-09更新随笔 / 优化几秒读完 (大约44个字)

Memory Cache

视频介绍：影响运行时间常数的因素 5 —— Memory Cache

CF博客：On Cache Friendliness

2024-01-01发表2024-01-08更新学习总结 / 图论 / 最短路几秒读完 (大约30个字)

最短路基础

前置知识：图论基础

Floyd算法

用于求解任意两点的最短路。

2024-01-01发表2024-01-09更新学习总结 / 图论 / 最短路6 分钟读完 (大约891个字)

最短路技巧

前置知识：图论基础，最短路基础

Super Root 超级源点、加点、加边

特征

需要添加边，但是暴力加边时间or空间复杂度不可取；
加边是针对某一类点加边；
答案最终会汇集到一个点上，一些网络流的题需要建立超级源点和超级汇点。

注意点

加边时考虑边权设计；
如果要对超级源点加双向边，要考虑周全一些不合法的情况，例如会不会无边权超级传送；
加点要算好空间，算好下标。

例题

给定一棵树，$1$ 为根节点，对于树上每条边 $(u, v)$ 都具有一个权值 $w$ 。但是，如果两个节点的高度差为 $k$ ，则可以通过 $p$ 的权值直接到达，求在这棵树上从 $s$ 到 $t$ 的最短路径长度。
多组测试数据。
$1 \le T \le 5$
$2 \le n \le 10^6$
$1 \le u_i,v_i,s,t \le n, u_i \neq v_i, s \neq t$
$1 \le w_i,k \le 10^6$
$0 \le p \le 10^6$

我们发现这道题需要加边跑最短路，然而，$\text{Dijkstra}$ 带上加边会跑到 $O((n+m+n^3)\log (m+n^3)+n^3)$ ，这里极限数据的情况是整棵树有 $\sqrt n$ 层，每层有 $\sqrt n$ 个点，且 $k = 1$ 。即使我们不真正连边，仍然还有 $O((n+m+n^3)\log (m+n^3))$ 的时间复杂度。~~死得透透的。~~

因此我们考虑对每一层建立一个超级源点，边权为 $0$ ，再对上下 $k$ 层的超级源点连边，因为这个点既可以上又可以下，所以要连双向边。然鹅，这个方案有一个巨大的问题。

如果我们连双向边，那么最短路会借助超级源点在同一层实现 $0$ 权值跳转，很明显，这是不合法的。于是我们考虑每层加两个超级源点，一个用于向外走，一个向内走，问题就解决了，时间复杂度 $O((5n+m)\log (2n+m))$ 。

给出一个图，每次只能连续走两条边，其权值为两条边权值的和的平方，求以 $1$ 为源点时分别到 $1\sim n$ 的最短路。
$2 \leqslant n \leqslant 10^5,1 \leqslant m\leqslant min(\frac{n(n-1)}{2},2*10^5)$
$1\leqslant v_i,u_i \leqslant n,1 \leqslant w_i \leqslant50,u_i\neq v_i$

同时处理两条边是有些困难的。考虑往图里增加信息。我们发现边权十分小，只有 $50$ 。于是我们想到建分层图，入边 $(u,v,w)$ 即建一条边从第 $w$ 层图 $v$ 点到原图 $v$ 点，出边 $(u,v,w)$ 就是建一条边从原图 $v$ 点到第 $w$ 层图 $v$ 点。这样做正确性显然。

2. 最短路计数

这里要提两个概念

附录

SPFA玄学优化

据某位不知名人士所言，SPFA的时间复杂度可以用 $O(m+n\log n)$ 来拟合，而Dijkstra的时间复杂度为 $O(m\log n)$ 。这意味着如果题目不卡SPFA，则SPFA跑得比Dijkstra还要快。如果卡SPFA，还可以通过SLF、mcfx等优化方法来使SPFA更快。甚至专门卡SPFA的标准版单源最短路径的次优解（$\text{80ms}$）就是使用了SLF-swap优化过的。

2023-12-30发表2024-01-09更新学习笔记8 分钟读完 (大约1160个字)

题目思路存储

奇怪的最短路问题

原题：HDU6166/P5304/LOJ#3087

法一

维护最短路和次短路以及它们的来源点。具体有待补充。

法二

一种套路：多源多汇最短路。

多源多汇怎么做？

建一个超级源点和超级汇点，但是这样从源点出来就可以0权到汇点。

解决方案：

随机划分：

$p=\frac{1}{4}$，T次成功概率：$1-(1-p)^T$，虽然 $20$ 次随机成功概率为 $99.68\%$，但毕竟是概率，不够靠谱并且基于RP。
二进制分组：

按照二进制的一个位置上的 $01$ 值来划分谁是源点谁是汇点，由数据范围知最多 $17$ 次划分，每次需要跑两遍。有点卡时限但能过。

指针分析

复习指针？

题目中给的关系实际上是一些边的关系，但是这些边有些限制。

某些边有激活条件，例如一个指针得先指向某个地址之后才能访问。

小模拟，将题目操作转化为代码。
Bellman-ford 思想：不断松弛，在过程中实现 $4$ 种操作并同时维护。
1. 实现思路1：set 维护每个点能到哪些点
2. 实现思路2：状态压缩
关于优化：
1. 基于RP：减少松弛轮数
2. 基于卡常：快读
3. 基于随机化：shuffle+clock() 卡时间

老算法焕发新生。

果国的奇妙旅行

带决策的期望。

#define 卡票

定义 $E(u)$ 表示 $u$ 到终点的期望。

此题目要求在最优策略下到终点的期望抽卡次数，可以发现所谓最优策略就是贪心：如果我抽到的卡走过去的期望 $E(v)$ 较 $E(u)$ 而言减小了，即 $E(u) > E(v)$，那么我们就可以走到 $v$，定义这就是一次成功的决策。

也就是说，如果我抽到的卡能使我的期望减小，那么就走，否则扔掉重来。于是我们的转移就可以分为两种情况：一种是 $v$ 向 $u$ 转移；另一种是不转移。

我们又发现，从结果来看，如果 $u$ 走到 $v$ 这个决策是成功的，那么 $v$ 走到 $u$ 的决策一定是不成功的，因为 $E(u) > E(v)$，就一定 $E(u) > E(v)$ （满篇废话，然而这种显著的废话往往是最难发现并利用的）。

综上，我们就认为 $u$ 的转移是有方向的。

根据以上的情况讨论，不难得到 $E(u)$ 转移如下：

$$E(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{\frac{E(v)}{deg(u)}}+\sum_{v\in e(u)}^{E(v)\geq E(u)}{\frac{E(u)}{deg(u)}}+1$$

设 $x=\sum[v\in e(u) \And E(v) \geq E(u)],d=deg(u)$

化简过程：

$$E(u)=\frac{1}{d}(\sum_{v\in e(u)}^{E(v) < E(u)}{E(v)}+xE(u))+1$$

$$dE(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{E(v)}+xE(u)+d$$

$$(d-x)E(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{E(v)}+d$$

得到：

$$E(u)=\sum_{v\in e(u)}^{E(v) < E(u)}{\frac{E(v)}{d-x}}+\frac{d}{d-x}$$

十分抽象的一点是：我确定边的方向需要 $u$ 和 $v$ 的期望来进行大小比较，然而期望又需要边的方向来更新。问题就是如何打破这个循环。

数学上的推导不太可能了，考虑从更新顺序入手。

目前这里的方法是填表法，考虑使用刷表法，即对于每个 $u$ 去更新它的 $v$。考虑使用Dijkstra算法。而且不难发现，$E(u)$ 的值随着更新不断减小（分母变大）。

像这种破逻辑的环很难解决，切入口不好找，因此这里直接放结论。

一开始设置 $E(u)=+\infty$ ，然后让 $E(v)$ 从小到大更新 $E(u)$ 。

（为什么这样可行我也不会证。可能需要数学归纳法。）

最后，因为 $E(u)$ 的定义是 $u$ 到终点的期望，因此搜索时应该从终点开始搜。（思考：从起点搜结果会受影响吗？）

推完了。

至于怎么实现还得是Dijkstra。

事实上，指针分析和果国的奇妙旅行都不是最短路的题目，但是借用了最短路算法的思想，不愧为《最新颖的一集》。

2023-12-28发表2024-01-09更新学习总结 / 考试9 分钟读完 (大约1413个字)

1005考试总结

1005比赛总结

时间线 Time Line

08:00 开始考试
08:00 开 $A$
09:45 结束 $A$，开 $B$
10:10 结束 $B$，开 $C$
11:00 开 $\text{Excel}$ ，跑 $C$ 大样例
11:45 结束 $C$，开 $D$
12:00 结束考试

结果 Result

$A;;40,pts.$ (低于预期)
$B;;80,pts.$ (高于预期)
$C;;35,pts.$ (低于预期)
$D;;0;,pts.$ ~~(不好评价)~~
$Total;;155,pts.$

从排名来看高于预期，从绝对得分来看符合预期。

总结 Summary

首先，这次比赛最大的一个问题是时间的安排，$A$ 与 $C$ 题均耗费了一个小时以上的时间，导致 $B$ 与 $C$ 题只有很少的时间写。戏剧性的是，$B$ 只耗费了 $25\text{min}$ 却是本场比赛中拿分最高的题。

其次则是思路上的问题，$A$ 题在赛时有正解的想法，但是因为没有仔细下去或是不敢往下想而放弃（那时已经 9:10 了，因此不敢拿剩下的时间去赌这道题）。$C$ 题也是如此，在提交代码后大约 $30\text{s}$ 就找的了赛时没找到的 BUG。

最后就是码力上的问题，其实也是因为思路被禁锢了，$C$ 题明明有一种写起来+调起来都更舒服的方式，可惜没想到，导致耗费了大量时间在调试上。

这告诉我什么？

及时止损，切换思路
提高码力，估准难度
仔细思考，加强深度
合理化时间分配
关于知识点的联系
暴力！暴力！暴力！！！不会也得打暴力！

第一阶段总结

第一阶段主要是关于动态规划的序列问题的，可以分为两种：

最长公共子序列（LCS）
最长上升子序列（LIS）

首先，LIS可以用来求LCS，其时间复杂度为 $O(n\log n)$ 。

最长公共子序列又有几个经典问题：

求长度（模板）
求方案数：动态规划+转移计数
求方案：动态规划+转移倒推
求字典序最小方案：动态规划+统计字母出现位置
给定两个字符串求最短包含串的方案（数）：动态规划+双指针

而最长上升子序列的问题就多了去了，以下只列一些：

求长度（模板）
求字典序最小/大方案（动态规划+贪心递推）
求方案数（动态规划+计数+ $O(n\log n)$ 树状数组或二分优化）
求本质不同的方案数（同上，加个去重）
求LCS（用一个序列“离散化”另一个序列）
判断一个数是否出现在LIS上（动态规划$O(n\log n)$+统计位置：一定在序列上的数位置不变，不一定则位置可能变化）
构造指定长度的LISDL序列（不好说）

一阶段的问题主要都体现在1005的比赛中了，比赛中的问题就是要解决的问题。

关于最长上升子序列的 $O(n\log n)$ 写法：

1. 二分

空间复杂度 $O(n)$ 即数组长度空间。

这种方法本身不能求出具体方案，可以求出最长上升子序列的长度。

其原理简单来说就是对于每次新加一个元素，看它是否能接着当前这个序列下去，如果不能，则找到最小的一个大于（等于）它的元素并替换。

代码实现如下：

memset(g, 0x3f, sizeof g);
int ans = 0;
for (int i = 1; i <= n; i++) {
	int p = lower_bound(g+1, g+n+1, a[i]) - g;
	g[p] = a[i];
	f[i] = p;
}
while (g[(++ans)+1] != inf) continue;

（f 数组的定义和朴素转移一样，$f_i$ 记录以 $a_i$ 结尾的最长上升子序列）

2. 树状数组

注意：本方法空间复杂度为 $O(k)$ （$k$ 是 $a_i$ 的取值范围）

所谓优化，要么在算法上优化，码量小，但难想；如果在数据结构上优化，码量大，但是基本不动脑子。

具体而言，我们做出如下分析：

优化什么？第二维 j 的转移。
怎么优化？树状数组，对值域开数组，每次转移拿当前的 $a_i$ 的值查询并更新树状数组。
如何证明正确性？感性理解，分析朴素转移中有哪些限制：①. $j<i$；②. $a_j<a_i$。①我们在循环更新的过程中从未往数组中加入 $i\leq j$ 的元素，自然也不会从后面的状态转移过来；②因为我们是对值域开数组，因此在当前 $a_i$ 前面的一定是那些 $a_j<a_i$ 的状态。

至此，所有问题均被解决，剩下的只是代码实现了（这里不贴代码了，待会连着统计方案数的题一起贴）。

注意树状数组只是优化哪些数能被转移以及加快转移过程，不是把 f 数组开到树状数组上！

有了这些法宝，接下来就看例题啦！

经典例题

例一

题目：给定字符串 $a$ 和 $b$ ，求最短的字符串 $c$ ，使得 $a$ 与 $b$ 均为 $c$ 的子序列。输出所有满足条件的 $c$ 中字典序最小的。

2023-12-28发表2024-01-09更新学习总结 / 图论2 分钟读完 (大约337个字)

图论基础

存图

邻接矩阵

实现：

int g[N][N];

g[u][v] = w;

for (int v = 1; v <= N; v++) {
    if (!g[u][v]) continue;
    // ...
}

空间复杂度：$O(n^2)$

优点

配合Floyd算法，效果嘎嘎好
支持随机访问，即直接查询某条边是否存在
代码好写

缺点

空间复杂度太高，是个硬伤

邻接表

实现：

vector<pair<int, int>> g[N];

g[u].push_back({v, w});

for (pair<int,int> i : g[u]) {
    int v = i.first, w = i.second;
    // ...
}

空间复杂度：$O(m)$

优点

空间复杂度小
同一个点空间连续，有效降低Memory Cache带来的时间花销
写循环遍历 $u$ 边时可以少写点代码：for (pair<int,int> i : g[u])

缺点

由于 vector ，空间复杂度要翻个倍，在卡空间的题目中它不是好选择
莫名其妙TLE（STL造成的）

链式前向星

实现：

struct node{
    int to, nxt, w;
}g[M];
int head[N], cnt;

void add(int u, int v, int w) {
    g[++cnt] = {v, head[u], w};
    head[u] = cnt;
}

for (int i = head[u]; i; i = g[i].nxt) {
    int v = g[i].to, w = g[i].w;
    // ...
}