Description
给定一个包含 \(n\) 个顶点和 \(m\) 条双向边的连通图，每条边的权重不超过 \(x\)。第 \(i\) 条边连接顶点 \(u_i\) 和 \(v_i\)，权重为 \(w_i\)，颜色为 \(c_i\)（\(1 \leq i \leq m\)，\(1 \leq u_i, v_i \leq n\)）。颜色 \(c_i\) 为红色（red）、绿色（green）或蓝色（blue）。保证图中至少存在一条每种颜色的边。
对于一条允许重复顶点和边的路径，设 \(s_r\)、\(s_g\)、\(s_b\) 分别表示路径中经过的红色、绿色和蓝色边的权重之和。若某条边被多次遍历，每次遍历均会被单独计数。
请找到从顶点 \(1\) 到顶点 \(n\) 的所有可能路径中，\(\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)\) 的最小值。
\(4 \leq n \leq 2 \cdot 10^5\)，\(n-1 \leq m \leq 2 \cdot 10^5\)，\(1 \leq x \leq 2 \cdot 10^5\)。
Solution
设 \(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(w_i)\)，则如果 \(r\) 能走出来，则 \(r+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\) 可以删掉，即让 \(M_0\leftarrow\gcd(M_0,\text{lcm}(M_1,M_2))\)。
这是因为这么操作完如果存在一个数 \(x\) 满足条件，那么每次让 \(x\) 加上 \(\text{lcm}(M_1,M_2)\)，总共加 \(\frac{\text{lcm}(M_0,M_1,M_2)}{\text{lcm}(M_1,M_2)}\) 轮，一定存在恰好一次满足原先的限制。
操作完后可以设 \(M_0=gab,M_1=gac,M_2=gbc\)，其中 \(a,b,c\) 两两互质。现在再去做最开始的暴力做法需要跑 \(\frac{\text{lcm}(M_0,M_1,M_2)}{\max\{M_0,M_1,M_2\}}\) 次，也就是 \(\min\{a,b,c\}\)，由于 \(ab,ac,bc\leq x\)，所以 \(\min\{a,b,c\}\leq\sqrt x\)，所以复杂度变为 \(O(\sqrt x)\)。
时间复杂度：\(O(n+m\log x+\sqrt x)\)。
Code
#include <bits/stdc++.h>// #define int int64_tconst int kMaxN = 2e5 + 5;int n, m, x;
int u[kMaxN], v[kMaxN], w[kMaxN], col[kMaxN], st[kMaxN];
bool f[kMaxN][8];
std::vector<int> G[kMaxN];int64_t lcm(int x, int y) { return 1ll * x / std::__gcd(x, y) * y; }void bfs() {std::queue<std::pair<int, int>> q;for (int i = 1; i <= n; ++i)for (int s = 0; s < 8; ++s)f[i][s] = 0;f[1][0] = 1, q.emplace(1, 0);for (; !q.empty();) {auto [u, s] = q.front(); q.pop();for (auto i : G[u]) {int v = ::u[i] ^ ::v[i] ^ u, w = st[i], t = s ^ w;if (!f[v][t]) f[v][t] = 1, q.emplace(v, t);}}
}void dickdreamer() {std::cin >> n >> m >> x;for (int i = 1; i <= n; ++i) G[i].clear();int g[3] = {0};for (int i = 1; i <= m; ++i) {std::string str;std::cin >> u[i] >> v[i] >> w[i] >> str;if (str[0] == 'r') g[0] = std::__gcd(g[0], w[i]), col[i] = 0;else if (str[0] == 'g') g[1] = std::__gcd(g[1], w[i]), col[i] = 1;else g[2] = std::__gcd(g[2], w[i]), col[i] = 2;G[u[i]].emplace_back(i), G[v[i]].emplace_back(i);}g[0] *= 2, g[1] *= 2, g[2] *= 2;for (int i = 1; i <= m; ++i) {if (w[i] % g[col[i]] == 0) st[i] = 0;else st[i] = (1 << col[i]);}bfs();int ans = 1e9;int MM[3] = {std::__gcd<int64_t>(g[0], lcm(g[1], g[2])), std::__gcd<int64_t>(g[1], lcm(g[0], g[2])), std::__gcd<int64_t>(g[2], lcm(g[0], g[1]))};int LCM = lcm(MM[0], lcm(MM[1], MM[2]));for (int s = 0; s < 8; ++s) {if (!f[n][s]) continue;int M[3] = {MM[0], MM[1], MM[2]};int R[3] = {(s & 1) * g[0] / 2 % M[0], (s >> 1 & 1) * g[1] / 2 % M[1], (s >> 2 & 1) * g[2] / 2 % M[2]};if (M[1] > std::max(M[0], M[2])) std::swap(M[0], M[1]), std::swap(R[0], R[1]);else if (M[2] > std::max(M[0], M[1])) std::swap(M[0], M[2]), std::swap(R[0], R[2]);for (int i = R[0]; i <= LCM + R[0]; i += M[0]) {if (i < R[1] || i < R[2]) continue;int id[2][2] = {{(i - R[1]) / M[1] * M[1] + R[1], (i - R[1]) / M[1] * M[1] + M[1] + R[1]},{(i - R[2]) / M[2] * M[2] + R[2], (i - R[2]) / M[2] * M[2] + M[2] + R[2]}};for (int o1 = 0; o1 < 2; ++o1)for (int o2 = 0; o2 < 2; ++o2)ans = std::min(ans, std::max({i, id[0][o1], id[1][o2]}) - std::min({i, id[0][o1], id[1][o2]}));}}std::cout << ans << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}