CF2077G RGB Walking 题解

题意简述

给定一张 $n$ 个点、$m$ 条边的连通无向图，每条边有权值 $w_i$（$w_i \le x$）和颜色（红/绿/蓝），保证每种颜色至少存在一条边。

我们可以走可重复经过点和边的路径，从 $1$ 号点走到 $n$ 号点。设路径中红、绿、蓝边的权值和为 $s_r,s_g,s_b$。

求 $\max(s_r,s_g,s_b) - \min(s_r,s_g,s_b)$ 的最小可能值。

数据范围：$4 \le n,m,x \le 2 \times 10^5$。

---

解法

设 $t_i$ 表示第 $i$ 条边经过的次数。

首先有一个显然的结论：可以把每个 $t_i$ 调整成一个很大的偶数，使得当前 $\max(s_r,s_g,s_b)-\min(s_r,s_g,s_b)=0$，之后只需要满足度数奇偶性限制，就能构造出合法路径。

单独对一种颜色考虑：对于一条边 $i$，令 $t_i \leftarrow t_i+2$，对应的行走方案依然合法，也就是说该颜色的权值和可以任意增加 $2\cdot w_i$。

设 $g$ 为该颜色所有边权的 $\gcd$，那么如果 $s$ 是一个可实现的权值和，则 $s+2g$ 也一定可实现。

因此我们只需要关心 $sum \bmod 2g$ 的值。又因为每条 $w_i$ 都是 $g$ 的倍数，所以余数只有两种可能，可以用 BFS 求出。

把三种颜色放在一起考虑，用一个大小为 $8$ 的状态将余数压缩，再跑一次 BFS，就能得到三个颜色同时合法的余数组合。

现在问题转化为：给定三个同余方程

$$x_i \equiv r_i \pmod{M_i}$$

求 $\max\{x_i\}-\min\{x_i\}$ 的最小值。

一个朴素思路是枚举任意一个 $x_i$，另外两个都只有 $O(1)$ 种可能取值，但暴力做复杂度为 $O(V^2)$。

注意到对某个 $M_i$，如果它含有一个质因子 $p$，而另外两个模数都不含 $p$，那么可以把这个 $p$ 去掉，即令：

$$M_0 \leftarrow \gcd(M_0,\operatorname{lcm}(M_1,M_2)) $$

原因是：操作之后若存在满足条件的 $x$，每次将 $x$ 加上 $\operatorname{lcm}(M_1,M_2)$，一共加 $\dfrac{\operatorname{lcm}(M_0,M_1,M_2)}{\operatorname{lcm}(M_1,M_2)}$ 轮，一定存在某一轮满足原限制。

操作后可以设

$$M_0=gab,\;M_1=gac,\;M_2=gbc$$

其中 $a,b,c$ 两两互质。再用朴素做法，只需要枚举

$$\frac{\operatorname{lcm}(M_0,M_1,M_2)}{\max\{M_0,M_1,M_2\}} $$

次，也就是 $\min\{a,b,c\}$ 次。 由于 $ab,ac,bc\le x$，所以 $\min\{a,b,c\}\le \sqrt x$，总复杂度降为 $O(x)$。

---

时间复杂度

$O(n + m\log x + x)$