省选-图论

· · 个人记录

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

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

经常会发出“这竟然是一道图论题！”这样的感叹（比如我 在做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*10}=f_{i}$ 和 $f_{i+1}=f_{i}+1$ 转移，相当于模拟数位进位，然后需要找到一个 $k$ 的倍数的。 `01` bfs 会更快。 ## P7515 [省选联考 2021 A 卷] 矩阵游戏 [P7515 [省选联考 2021 A 卷] 矩阵游戏](https://www.luogu.com.cn/problem/P7515)。 不是，这玩意儿如果不是在图论里我绝对想不到图论。 首先，我们先当这不是个图论题。 稍微尝试一下就会发现题目最恶心的限制是 `其每个元素为大小不超过 $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} $$ ::::info[警示后人] 首先是多测没清空，需要仔细检查，比如记录负环的 `cnt` 数组，或者你让 $0$ 作为超级源点，这也要清空（虽然不会错）。 还有就是你如果用 `cin/cout` 并且关闭了同步，需要注意不能与其他输出方式混用，不要为了省事写 `puts`。 还有就是提醒一下 TLE50 的，建议稠密图用 vector。 :::: ## P5905 【模板】全源最短路（Johnson） [P5905 【模板】全源最短路（Johnson）](https://www.luogu.com.cn/problem/P5905)。 我们想用 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] 最小生成树计数](https://www.luogu.com.cn/problem/P4208)。 性质：对于任意一个带权无向图，其所有可能的最小生成树中，每种权值的边的数量是固定的，即由该权值的边组成的多重集合（考虑边权）在所有最小生成树中是完全相同的。 证明可以用 Kruscal 的过程证明。 还需要一个性质： 在处理完所有权值小于等于某个值 $w$ 的边后，图中顶点被分成的连通块（即哪些顶点在同一个连通分量中）在所有不同的最小生成树中是完全一致的。 如果不一致，那后面加的边一定没有前面优。 有了这两点性质，我们就可以做这道题了（不用矩阵树定理也行）。 ## CF888G Xor-MST [CF888G Xor-MST](https://www.luogu.com.cn/problem/CF888G)。 这道题是用 Boruvka 算法。Boruvka 大概是对于每一个联通块，找出离他最近的块连接，循环这个操作。 ## P5236 【模板】静态仙人掌 [P5236 【模板】静态仙人掌](https://www.luogu.com.cn/problem/P5236)。 [这篇 tj](https://www.luogu.com.cn/article/7hnuf036) 讲的还是很清楚的。 # 2-SAT ## P5332 [JSOI2019] 精准预测 [P5332 [JSOI2019] 精准预测](https://www.luogu.com.cn/problem/P5332)。 这道题是 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$ 就是离散化后找到下一个。