【数论+并查集】Walk on Graph

题目

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

思路

考虑把这个过程倒过来，这样每走一次就会变成 $2x+w$。

朴素做法是判断到某个点，值为 $x$ 是否可行，考虑寻找一些性质来优化这个做法。

不难发现直接做的话是单向边，这样处理起来比较困难。

考虑一条边 $(u,v,w)$，如果在这条边上进行左右横跳的话，可以从 $(u,x)$ 转移到 $(v,2x+w)$，即一个状态有唯一后继。同时因为模数为奇数，这一过程是可逆的，所以一个状态有唯一前驱。因此这会形成一个环。我们不断在这个环上走，可以从 $(v,2x+w)$ 走到 $(u,x)$。因此可达性是双向的。

考虑一个点的某两条出边 $(a,b,w_1),(a,c,w_2)$，那么可以得到状态 $(a,4x+3w_1),(a,4x+3w_2)$，因此 $(a,x)$ 和 $(a,x+3(w_1-w_2))$ 是互相可达的。显然这个连通块中任意一个点 $p$ 都满足 $(p,x)$ 和 $(p,x+3(w_1-w_2))$ 是互相可达的。

考虑如果一对边边权的差为 $d$，那么我可以让 $(p,x)$ 到达 $(p,x+3d)$ 。证明考虑从一条边到另外一条边的路径，不难用中间的点来得到这个差。

因此设所有边两两之差的最大公约数为 $d$，设 $g=(MOD,3d)$，那么 $(p,x)$ 和 $(p,x+g)$ 都是可以互相到达的。

注意到此时任意一条边的边权为 $kd+r$。先考虑一下 $r=0$ 怎么做。此时任意一个点的状态都可以表示为 $td$，我们可以把值对 $g$ 取模，因此我们只关心 $t$ 对 $3$ 取模后的余数。然后就是一个点数只有 $3n$ 的图判断连通性，直接并查集维护就行了。

现在考虑 $r\ne 0$ 的情形。注意到所有边的 $r$ 都是相同的，最终路径的权值是 ${\sum }_i{2}^i(k_{i}d+r)=kd+(2^l-1)r$ 。现在比较难处理的问题是 $2^l-1$。考虑左后横跳可以在不改变 $k\mathrm{m}\mathrm{o}\mathrm{d}3$ 的情况下使得 $l$ 增加 2。因此枚举 $k$ 和 $l$ 的奇偶性，判断是否存在一个 $l$ 使得 $kd+(2^l-1)r=R$。现在状态数只有 $6n$ 并查集维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+77;
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]);
}
int gcd(int x,int y)
{
	if(y==0) return x;
	return gcd(y,x%y);
}
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);
	for(int i=1; i<=m; i++)
	{
		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;
	for(int i=0; i<=6*n; i++) fa[i]=i;
	for(int i=1; i<=m; i++)
	{
		int w=(c[i]-z)/g;
		for(int p=0; p<=1; p++) for(int q=0; q<=2; q++)
		{
			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;
		for(int p=0; p<=1; p++) for(int q=0; q<=2; q++) if(get(Id(t,0,0))==get(Id(s,p,q))) ret|=can[p][(r+z+(3-q)*g)%mod];
		puts(ret?"YES":"NO");
	}
}

最后

以上就是单纯凉面为你收集整理的【数论+并查集】Walk on Graph的全部内容，希望文章能够帮你解决【数论+并查集】Walk on Graph所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。