[AGC031F]Walk on Graph

89 阅读 0 评论 59 点赞

我是靠谱客的博主温暖方盒，最近开发中收集的这篇文章主要介绍[AGC031F]Walk on Graph，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

有一张n个点m条边的无向连通图G，每条边有长度ci，有一个人在上面走
有q组询问，每组询问给出si,ti,ri，表示问你是否存在一条从si出发到ti结束长度为ri%Mod的路径
注意这里的路径长度是∑ci*2^i
n,m,q<=50000,Mod<=1000000且Mod为奇数

Solution

考虑这样一个东西，这个人最开始在ti，然后每走一条边边权会*2+C
状态可以表示为二元组 $(u, x)$ 表示在点u数为x，这样直接连边得到了一个nMod的做法
这里可以直接连无向边是因为Mod为奇数，那么我们可以从 $(u, x) - > (v, 2 x + c) - > (u, 4 x + 3 c) - > . . . .$ 最后一定能回到自己，你可以看成在模意义下走了一个偶环
然后注意到如果有两条边 $(u, v, c), (u, w, c^{'})$ ，那么你可以达到 $(u, 4 x + 3 c) 和 (u, 4 x + 3 c^{'})$
也就是说你可以从 $(u, x)$ 到 $(u, x + 3 (c - c^{'}))$ ，那么我们把所有有公共点的边的差值求个gcd，设为g
因为图连通，这个g也是两两边差值的gcd(根据辗转相除可以加
那么我们可以把Mod变为 $g c d (3 g, M o d)$ 这个问题是不变的
注意到这时候所有边权%g都是一样的，设为z
我们可以把所有状态的第二位抬高z，边权-z，注意到 $(u, x^{'}) - > (v, 2 (x^{'} - z) + (c^{'} + z) + z) = (v, 2 x^{'} + c^{'})$ ，所以在这种意义下我们的运算是不变的
于是我们可以把所有边权看做是g的倍数，那么我们一个状态 $(u, x)$ 可以转移到的状态为 $v,2^px+qg)$ ，考虑Mod|3g所以 $q \in [0, 1, 2]$
现在我们只需要把p优化下来，还是考虑 $(u, x) - > (v, 2 x + c) - > (u, 4 x + 3 c) = (u, 4 x)$ 也就是说可以把所有的p按奇偶分类，相同类别的都是互相可达的
那么我们就得到了一张点数为6n的图，那一个并查集就知道了两两的连通性
考虑询问 $(s, t, r)$ ，相当于问能否从 $(t, z)$ 走到 $(s, z + r)$ ，我们枚举q和p的奇偶性，相当于问是否存在一个p，满足 $z2^p+qg=z+r$ ，等价于问 $z + r - q g$ 能不能被表示为z乘2的奇数/偶数次幂，这个可以对[0,Mod)里面的数都预处理一下
那么总复杂度就是 $O (M o d + (n + q + m) α (n))$

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int N=1e6+5;

int n,m,q,mod,s,t,r,u[N],v[N],c[N],g,fa[N];
bool can[2][N];

int Id(int x,int y,int z) {return (x-1)*6+y*3+z;}
int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);}

void link(int x,int y) {
	x=get(x);y=get(y);
	if (x==y) return;
	fa[x]=y;
}

int main() {
	scanf("%d%d%d%d",&n,&m,&q,&mod);
	fo(i,1,m) {
		scanf("%d%d%d",&u[i],&v[i],&c[i]);
		g=__gcd(g,abs(c[i]-c[1]));
	}
	if (!g) g=mod;mod=__gcd(mod,3*g);int z=c[1]%g;
	fo(i,0,6*n) fa[i]=i;
	fo(i,1,m) {
		int w=(c[i]-z)/g;
		fo(p,0,1)
			fo(q,0,2) {
				link(Id(u[i],p,q),Id(v[i],1-p,(2*q+w)%3));
				link(Id(v[i],p,q),Id(u[i],1-p,(2*q+w)%3));
			}
	}
	for(int i=0,j=z;i<mod<<1;i++,(j<<=1)%=mod) can[i&1][j]=1;
	for(;q;q--) {
		scanf("%d%d%d",&s,&t,&r);
		int ret=0;
		fo(p,0,1) fo(q,0,2) if (get(Id(t,0,0))==get(Id(s,p,q))) ret|=can[p][(r+z+(3-q)*g)%mod];
		puts(ret?"YES":"NO");
	}
	return 0;
}