很多人说，图论就是背模板。

对于算法来讲是如此，但是我们在做题的时候，遇到的最大 的问题其实是如何转化为图论模型。

经常会发出“这竟然是一道图论题！”这样的感叹（比如我 在做2021年联合省选的时候）。

所以这节课，不仅介绍一些经典算法模型，选择的例题多为 需要转化问题的题目。

最短路

P6961 [NEERC 2017] Journey from Petersburg to Moscow

P6961 [NEERC 2017] Journey from Petersburg to Moscow。

用到了图论中的经典技巧，以 $0$ 为分界点。

枚举每一条边为第 $k$ 大的情况，然后将所有边的边权减去这条边的边权，然后将负数变成 $0$。

这样的话，比 $k$ 大的就不用算了。

然后怎么证明这个的正确性呢？

如果真实的比 $k$ 小，也就是 $0$ 多了，这样的话答案一定会更大，因为减去的要加回来。

如果真实的比 $k$ 大，也就是有很多没减成 $0$ 的，这就会导致程序考虑不需要考虑的东西，答案就更大了。

P5304 [GXOI/GZOI2019] 旅行者

P5304 [GXOI/GZOI2019] 旅行者。

建立超级源点和超级汇点。

然后需要找到超级源点到超级汇点的路径。

不能分治，因为分治太慢了，节点需要全部用满。

然后我们想到了二进制分组，就是进行 $\log$ 次，然后每一位相同的分在一起。这样不重不漏。

---

怎么更快？

换一个思路，枚举中间的点，然后看到他最近和他能到的最近的点凑成的路径。

两次 dij 可以完成。

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus。

好好读题，是一开始就反转。

好像不是分层图，因为这次翻转对下次有影响。

暴力就是枚举每条边翻转，然后 dij。

我们发现没有必要，因为如果这条边不是最短路上必经的边直接做对答案没有任何影响。

枚举每一条边，如果不是 $1\to n$ 或者 $n\to 1$ 的必经边，就可以直接贡献答案。

如果是的话，需要反转了再 dij。

这样复杂度是正确的，dij 用 $n^2$ 的。

P2371 [国家集训队] 墨墨的等式

P2371 [国家集训队] 墨墨的等式。

经典的同余最短路模板题。

首先差分一下，$ask(r)-ask(l-1)$。

然后我们发现，我们可以先找出最小的 $a_i$，然后每一个可行的 $b_i$，$b_i+a_i$ 也可行，所以只需要找到最小的 $\bmod~a_i$ 是每一个值的就行了。

然后有一个很阴的 Hack，最小的 $a_1$ 是 $0$，可以选择最大的。

P9140 [THUPC 2023 初赛] 背包

P9140 [THUPC 2023 初赛] 背包。

同余最短路。

选择性价比最高的物品的体积来作为同余最短路的那个模数。

对于 $V1=V2 \pmod {mod}, V1<V2$ 的，需要比较 $\frac{V2-V1}{mod}\times w+W1$ 和 $W2$，相当于比较 $W-\lfloor \frac{V}{mod} \rfloor\times w$。

然后需要结合数据范围中 $V$ 很大来说明，因为只有这样，$V$ 的实际大小才没有影响。然后数据范围保证了 $V\le mod^2$，所以是可以的。

最后答案就是 $\lfloor \frac{qv}{v} \rfloor\times w+dis_v, v=qv \mod mod$。

Trick：为了防止负权边，而且解决要求的是最大路径的，还需要处理一下，$v_i*w-c_i*m$ 就是相对于最大的扣除的贡献（其中这个式子同时乘了 $m$），这个代价需要最小。

最后的结果：$k\times w+\frac{r\times w-dis_r}{m}=\frac{v\times w-dis_r}{m}$。

AT_arc084_b [ABC077D] Small Multiple

AT_arc084_b [ABC077D] Small Multiple。

编号怎么乱了？

如果这不放在图论里，我显然不会用图论做。

$f_i$ 表示对 $k$ 取模为 $i$ 的数位和的最小值。

就是同余最短路。

$f_{i*10}=f_{i}$ 和 $f_{i+1}=f_{i}+1$ 转移，相当于模拟数位进位，然后需要找到一个 $k$ 的倍数的。

01 bfs 会更快。

P7515 [省选联考 2021 A 卷] 矩阵游戏

P7515 [省选联考 2021 A 卷] 矩阵游戏。

不是，这玩意儿如果不是在图论里我绝对想不到图论。

首先，我们先当这不是个图论题。

稍微尝试一下就会发现题目最恶心的限制是 其每个元素为大小不超过 $10^6$ 的非负整数。

因为我们可以先瞎写出第一行和第一列的，然后后面的就可以直接确定了。

然后令现在的为 $a$ 数组。

我们需要调整 $a$ 数组，可以这样：

（不想写表格，ctj 不过分吧）

$$\begin{bmatrix}a_{1, 1}+c_1 + d_1&a_{1, 2}-c_1 + d_2&a_{1, 3}+c_1+d_3&a_{1, 4} -c_1 + d_4 & \cdots\\a_{2, 1}+c_2 - d_1&a_{2, 2}-c_2 - d_2&a_{2, 3}+c_2-d_3&a_{2, 4} -c_2 - d_4 & \cdots\\a_{3, 1}+c_3 + d_1&a_{3, 2}-c_3 + d_2&a_{3, 3}+c_3+d_3&a_{3, 4} -c_3 + d_4 & \cdots\\a_{4, 1}+c_4 - d_1&a_{4, 2}-c_4 - d_2&a_{4, 3}+c_4-d_3&a_{4, 4} -c_4 - d_4 & \cdots\\\vdots&\vdots&\vdots&\vdots&\ddots\end{bmatrix}$$

我们将限制条件写出来：

$$\begin{cases}0\le a_{i, j}+c_i+d_j \le 10^6, i\equiv1\pmod 2\wedge j\equiv1\pmod 2\\ 0\le a_{i, j}-c_i+d_j \le 10^6, i\equiv1\pmod 2\wedge j\equiv0\pmod 2\\ 0\le a_{i, j}+c_i-d_j \le 10^6, i\equiv0\pmod 2\wedge j\equiv1\pmod 2\\ 0\le a_{i, j}-c_i-d_j \le 10^6, i\equiv0\pmod 2\wedge j\equiv0\pmod 2\end{cases}$$

这还是没法做，但是这让人想起了差分约束。

然后换一下元，让 $x_i = (-1)^i \times c_i$，$y_i = (-1)^{i+1}\times d_i$。

$$\begin{cases}0\le a_{i, j}-x_i+y_j \le 10^6, i\equiv1\pmod 2\wedge j\equiv1\pmod 2\\ 0\le a_{i, j}+x_i-y_j \le 10^6, i\equiv0\pmod 2\wedge j\equiv1\pmod 2\\ 0\le a_{i, j}+x_i-y_j \le 10^6, i\equiv1\pmod 2\wedge j\equiv0\pmod 2\\ 0\le a_{i, j}-x_i+y_j \le 10^6, i\equiv0\pmod 2\wedge j\equiv0\pmod 2\end{cases}$$ $$\begin{cases} x_i-y_j\le a_{i, j},y_j-x_i\le10^6-a_{i,j} , i=j\pmod 2 \\ y_j-x_i\le a_{i, j},x_i-y_j\le10^6-a_{i,j} , i \ne j\pmod 2 \end{cases}$$

警示后人

首先是多测没清空，需要仔细检查，比如记录负环的 cnt 数组，或者你让 $0$ 作为超级源点，这也要清空（虽然不会错）。

还有就是你如果用 cin/cout 并且关闭了同步，需要注意不能与其他输出方式混用，不要为了省事写 puts。

还有就是提醒一下 TLE50 的，建议稠密图用 vector。

P5905 【模板】全源最短路（Johnson）

P5905 【模板】全源最短路（Johnson）。

我们想用 dij，但是发现有负权边。

所以我们需要改一下形式，边权变成 $w+d_u-d_v$。（如果是 $w-d_u+d_v$ 需要反边，有点麻烦吧）

然后 $d$ 需要保证每一个 $w+d_u-d_v$ 都大于等于 $0$，我们发现这是三角形不等式，$w+d_u\ge d_v$，使用 SPFA 预处理。

然后就可以 dij 了，最后的 dis 需要 $-d_i+d_j$。

最小生成树

常见性质：

同一权值边的数量固定

对于任意一个带权无向图，其所有可能的最小生成树中，每种权值的边的数量是固定的，即由该权值的边组成的多重集合（考虑边权）在所有最小生成树中是完全相同的。

最小生成树是瓶颈生成树的充分不必要条件

无向图 $G$ 的瓶颈生成树是这样的一个生成树，它的最大的边权值在 $G$ 的所有生成树中最小。最小生成树是瓶颈生成树的充分不必要条件。

反证法，如果最小生成树的最大的边拆掉，换成瓶颈生成树中的一条将会得到更小的生成树。

P4208 [JSOI2008] 最小生成树计数

P4208 [JSOI2008] 最小生成树计数。

性质：对于任意一个带权无向图，其所有可能的最小生成树中，每种权值的边的数量是固定的，即由该权值的边组成的多重集合（考虑边权）在所有最小生成树中是完全相同的。

证明可以用 Kruscal 的过程证明。

还需要一个性质：

在处理完所有权值小于等于某个值 $w$ 的边后，图中顶点被分成的连通块（即哪些顶点在同一个连通分量中）在所有不同的最小生成树中是完全一致的。

如果不一致，那后面加的边一定没有前面优。

有了这两点性质，我们就可以做这道题了（不用矩阵树定理也行）。

CF888G Xor-MST

CF888G Xor-MST。

这道题是用 Boruvka 算法。Boruvka 大概是对于每一个联通块，找出离他最近的块连接，循环这个操作。

P5236 【模板】静态仙人掌

P5236 【模板】静态仙人掌。

这篇 tj 讲的还是很清楚的。

2-SAT

P5332 [JSOI2019] 精准预测

P5332 [JSOI2019] 精准预测。

这道题是 2-sat。

建边什么的还是比较模板的，就是二维，点 $(x,t)$ 表示 $x$ 在时间 $t$ 活着。

如果 $(x,t)$ 死了，那么 $(x,t+1)$ 也一定死。

还有就是预言，$0$ 的话 $\neg(x,t)\to \neg (y,t+1)$，$1$ 就是 $(x,t)\to \neg (y,t+1)$。

第一个问题：建不下图，因为点太多了，所以我们可以只保存有需要的，然后就可以了。至于 $t+1$ 就是离散化后找到下一个。