Phoenix and Odometers | Codeforces 1515G

题目链接

给定一张 \(n\) 个点 \(m\) 条边的带权有向图。

\(q\) 次询问,每次给定 \(v,s,t\),问是否存在一条起点终点都为 \(v\) 的路径满足 \(t | (s+l)\),其中 \(l\) 是路径的总长。

\(n, m,q \le 2 \cdot 10^5,s<t\le 10^9\),边权均不超过 \(10^9\)

首先这条路径只能在 \(v\) 所在强连通分量的内部。

以下所有的路径长度都是在模 \(t\) 意义下的。

引理:在同一个强连通分量,如果 \(u\rightarrow v\) 存在一条长度为 \(l\) 的路径,那么 \(v\rightarrow u\) 存在一条长度为 \(-l\) 的路径。

构造:假设 \(v\rightarrow u\) 存在一条长度为 \(w\) 的路径,先走 \(v\rightarrow u\),长度为 \(w\),再走 \(t-1\)\(u\rightarrow v\rightarrow u\),长度为 \((t-1)(l+w)\),总长度 \(-w\)

在强连通分量的内部,对于一个长度为 \(w\) 的环,从环上一个点 \(u\) 出发绕若干圈再回到 \(u\),所有可能的路径长度为 \(\gcd(w,t)\) 的倍数。根据引理,\(v\rightarrow u\) 有一条长度为 \(w\) 的路径,\(u\rightarrow v\) 有一条长度为 \(-w\) 的路径,先走 \(v\rightarrow u\),再绕若干圈,最后走 \(u\rightarrow v\),就可以凑出所有长度为 \(\gcd(w,t)\) 倍数的环。

\(r\) 为根建出 DFS 树,设 \(\phi(u)\) 表示从 \(r\) 沿着树边走到 \(u\) 的路径长度,对于每条非树边 \((u,v,w)\),意味着存在一个长度为 \(\phi(u)+w-\phi(v)\) 的环。设 \(x=\gcd_{(u,v,w)}\phi(u)+w-\phi(v)\),那么所有的可能环长分别为 \(0,x,2x,3x,\cdots\)。这些环长显然能取到,也可以归纳证明对于任何 \(r\rightarrow u\) 的路径,都有长度 \(\equiv \phi(u)\pmod x\)。结论:存在合法路径当且仅当 \(x|s\)

复杂度 \(O(n+m)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define upd(a, b) (a = min(a, b))

using namespace std;

typedef long long ll;
const int N = 2e5 + 5;

int n, m, q;
vector<pair<int, int>> G[N];
int idx, dfn[N], scc[N], stk[N], tp, sid;
ll g[N], d[N], gg[N];

int dfs(int u) {
int low = dfn[u] = ++idx; stk[++tp] = u;
for(auto [v, w] : G[u]) if(!dfn[v]) d[v] = d[u] + w, upd(low, dfs(v));
else if(!scc[v]) upd(low, dfn[v]), g[u] = gcd(g[u], d[u] - d[v] + w);
if(low == dfn[u]) for(int v = (sid++, 0); v ^ u;)
v = stk[tp--], scc[v] = sid, gg[sid] = gcd(gg[sid], g[v]);
return low;
}
int main() {
cin >> n >> m;
int u, v, w;
rep(i, 1, m) scanf("%d%d%d", &u, &v, &w), G[u].emplace_back(v, w);
rep(i, 1, n) if(!dfn[i]) dfs(i);
for(cin >> q; q--; puts(v % gcd(gg[scc[u]], (ll)w) ? "NO" : "YES"))
scanf("%d%d%d", &u, &v, &w);
}