主题

主题

 
   

4537: [Hnoi2016]最小公倍数

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4537/http://cogs.pro/cogs/problem/problem.php?pid=2241

Description

  给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n),每条边上带有权值。所有权值都可以分解成2^a*3^b的形式。

现在有q个询问,每次询问给定四个参数u、v、a和b,请你求出是否存在一条顶点u到v之间的路径,使得路径依次经过的边上的权值的最小公倍数为2^a*3^b。

注意:路径可以不是简单路径。下面是一些可能有用的定义:

最小公倍数:K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。路径:路径P:P1,P2,…,Pk是顶点序列,满足对于任意1<=i<k,节点Pi和Pi+1之间都有边相连。

简单路径:如果路径P:P1,P2,…,Pk中,对于任意1<=s≠t<=k都有Ps≠Pt,那么称路径为简单路径。

Input

  输入文件的第一行包含两个整数N和M,分别代表图的顶点数和边数。接下来M行,每行包含四个整数u、v、a、b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q,代表询问数。接下来q行,每行包含四个整数u、v、a和b,代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9

Output

  对于每次询问,如果存在满足条件的路径,则输出一行Yes,否则输出一行 No(注意:第一个字母大写,其余字母小写) 。

Sample Input

4 5

1 2 1 3

1 3 1 2

1 4 2 1

2 4 3 2

3 4 2 2

1 4 3 3

4 2 2 3

1 3 2 2

2 3 2 2

1 3 4 4

Sample Output

Yes

Yes 

Yes 

No 

No 


个人解法:

我们先把边按照a为第一关键字,b为第二关键字排序。询问也是如此。

之后对边分块。处理a 小于 这个块中边的a的最大值 的询问。

我们扫描每一个块,假设是第i块,就把1到i-1块的所有边按照b排序,这些边的a全部符合要求的。

询问也是一样按照b排序。

扫描每一个询问,用一个指针维护[1..i-1]的块b小于或者等于当前询问的b的边。然后扫描第i块的边,把符合要求的加入。

然后用一种可以分裂的数据结构维护联通块最大值。比方说并查集。之后再删除第i块的边。

这样保证了当前询问时,所有合法且会被考虑的边都加入,对并查集造成了贡献。我们只需要查询u与v是否在同一个联通块,以及u与v联通块的a与b的最大值即可。

复杂度证明:

  1. 每个块只会枚举n条边。最多有Num/Threshold个块。

  2. 一个询问只会多枚举threshold条边。最多q个询问。



细节问题:

  1. 有一个细节,如果存在同一个a有很多条边,这个算法正确性如何保证?可能一块不能包含所有的a相同的边。只处理a严格小于当前块里面的a的最大值的询问就可以了。

  2. 关于记录联通块a的最大值的maxa数组与记录联通块b的最大值的maxb数组,初始化应该是-1而不是0,因为存在0这个权值。


代码如下:

https://code.csdn.net/snippets/2260031


数据还挺给力的。在记录联通块maxa与maxb的时候,没有写a=0或者b=0的情况。其实编程序的时候想到了这个问题,然而没有及时做下批注……然后就忘了。

然而出题人有60分都卡了这里。真是悲惨……

(是不是我写了这么久然后也就就是一个40分的结果?方)

 
 
评论