250525 模拟赛 T2 题解

题意

给定一张无向图，包含 \(n\) 个点和 \(m\) 条边（可能包含重边自环），边有边权。有 \(q\) 次询问，每次询问给定 \(x,y,d\)，询问 \(x\) 和 \(y\) 之间是否存在一条路径（可以经过同一个点或边多次），其长度为 \(d\) 的整数倍。输出 Yes 或 No。

\(n,m\le 10^6,\ w\le 2^{60}-1\)

部分分：保证所有边权等于 \(1\)，所有询问 \(d=2\)。

题解

当 \(x\) 和 \(y\) 不在同一个连通块时，答案显然为 No。现在我们考虑同一个连通块中的情况。

考虑部分分。注意到如果连通块内存在奇环，则我们可以随意改变路径的奇偶性，因此这种情况答案一定是 Yes。否则，图是一个二分图，我们只需要判断 \(x,y\) 是否在图的同一侧即可。

考虑普通情况。继续观察，容易发现当 \(d\) 是奇数时，我们只需要找到 \(x\to y\) 的一条路径，然后在路径上走 \(d\) 次即可。

考虑推广这个结论：容易发现，这本质上是把一段长度为 \(l\) 的路径乘上了任意的奇数 \(p\)（上面 \(p=d\)），并且过程是充要的。因此我们可以把 \(d\) 拆分成 \(l\times p\)，取 \(l=2^k\)，\(k\) 即 \(d\) 中质因子 \(2\) 的次数。这样，问题就转化为找到一条被 \(d=2^k\) 整除的路径。

仍然先考虑有奇环的情况。由于边权边权不一定 \(=1\)，此处的奇环定义为权值和为奇数的环。由于一个奇数一定和 \(2^k\) 互质，因此我们可以通过这个环构造出 \(1\pmod {2^k}\)，由此可以直接构造出答案。

否则，图是一个二分图：奇数边跨过两个集合，偶数边两个端点都在同一个集合内。若 \(x,y\) 分布在两个集合中，那么所有 \(x\to y\) 的路径权值和都是奇数，一定不行。若 \(x,y\) 位于同一个集合内，我们先随便找出一条 \(x\to y\) 的路径，路径包含至少一条奇数边，权值和为 \(s\)（有 \(2\mid s\)）。任选路径中一条奇数边，记其权值为 \(w\)，我们希望找到一个满足 \(s+2qw\equiv 0\pmod {2^k}\) 的正整数 \(q\)。注意到这个式子等价于 \(\frac{s}{2}+qw\equiv 0\pmod {2^{k-1}}\)，显然有解（\(w\) 与 \(2^{k-1}\) 互质）。

然而，我们假设了图中存在一条奇数边，这不一定成立。这时，我们可以取连通块中所有边权的 \(\operatorname{gcd}\)，记其中 \(2\) 的次数为 \(p_2\)。如果 \(k\le p_2\)，显然有解；否则我们将所有边权都除以 \(2^{p_2}\)，这样至少会产生一条奇数边，就转换为上面的情况。

AC 代码

#include<iostream>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v, w, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, m, q, o;

int nn;
int col[N], scol[N], ok[N], p2[N];

void dfs1(int u) {
    col[u] = nn;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v, w = pool[i].w;
        if(w) p2[nn] = min(p2[nn], w & -w);
        if(!col[v]) dfs1(v);
    }
}

void dfs2(int u) {
    if(!scol[u]) scol[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v, w = pool[i].w;
        w /= p2[col[u]];
        if(w & 1) {
            if(scol[v] && scol[v] == scol[u]) ok[col[u]] = 1;
            if(!scol[v]) {
                scol[v] = 3 - scol[u];
                dfs2(v);
            }
        } else {
            if(scol[v] && scol[v] != scol[u]) ok[col[u]] = 1;
            if(!scol[v]) {
                scol[v] = scol[u];
                dfs2(v);
            }
        }
    }
}

int col0[N], nn0;
void dfs0(int u) {
    col0[u] = nn0;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v, w = pool[i].w;
        if(w) continue;
        if(col0[v]) continue;
        dfs0(v);
    }
}

signed main() {

    cin >> n >> m >> q >> o;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    for(int i = 1; i <= n; i++) p2[i] = INF;

    for(int i = 1; i <= n; i++) {
        if(!col[i]) {
            ++nn;
            dfs1(i);
            if(p2[nn] == INF) p2[nn] = 1;
            // cerr << p2[nn] << endl;
            dfs2(i);
        }
        if(!col0[i]) {
            ++nn0;
            dfs0(i);
        }
    }

#define NO { cout << "villea\n"; continue; }
#define YES { cout << "bougain\n"; continue; }

    while(q--) {
        int u, v, w;
        cin >> u >> v >> w;
        if(w == 0) {
            if(col0[u] == col0[v]) YES
            else NO
        }
        w = w & -w;
        if(col[u] != col[v]) NO
        if(ok[col[u]]) YES
        if(w <= p2[col[u]]) YES
        if(scol[u] == scol[v]) YES
        NO
    }

    return 0;
}