Phoenix and Odometers | Codeforces 1515G

发表于 分类于 本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目链接

给定一张 \(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);
}