[Hnoi2016 day1]最小公倍数
问题描述
给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成$2^a3^b$的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得路径依次经过的边上的权值的最小公倍数为$2^a3^b$。注意：路径可以不是简单路径。下面是一些可能有用的定义：最小公倍数：K个数$a_1,a_2,…,a_k$的最小公倍数是能被每个$a_i$整除的最小正整数。路径：路径$P:P_1,P_2,…,P_k$是顶点序列，满足对于任意$1<=i<k$，节点$P_i$和$P_{i+1}$之间都有边相连。简单路径：如果路径$P:P_1,P_2,…,P_k$中，对于任意$1<=s≠t<=k$都有$P_s≠P_t$，那么称路径为简单路径。
输入格式
第一行包含两个整数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$
输出格式
对于每次询问，如果存在满足条件的路径，则输出一行Yes，否则输出一行 No（注意：第一个字母大写，其余字母小写） 。
样例输入
4 5
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4
样例输出
Yes
Yes
Yes
No
No
首先容易想到一个朴素的暴力，即对每个询问，将满足$a_i<=a\&\&b_i<=b$的所有边拿来做一次并查集，然后如果$u,v$在同一个集合中，且这个集合中$Maxa==a\&\&Maxb==b$，那么就存在可行路径。这样做是$O(qm)$的，可以用分块优化。
考虑将边按照$a_i$排序后分组，分成$\sqrt{m}$组，将每个询问插入到对应的组中，对应的组的意思是对于组$i$中第一个元素$a_{询问}>=a_i$,且对于组$i+1$的第一个元素，$a_{询问}<a_{i+1}$
这样分组后，依次处理每一组的询问，注意到对于组$i$中的询问，前$i-1$组的$a_i$值一定是满足要求的，因此只需要将前$i-1$组中$b_i$也满足要求的插入并查集，因此可以将询问和前$i-1$组的边按照$b_i$排序，这样就可以每组询问$O(m)$处理了，然后对于同组中的边，直接暴力判断是否加入并查集中，然后处理下一个询问时还原并查集，这样的话每个询问的复杂度是$O(\sqrt{m})$的
然后这里的排序可以利用归并排序优化，总复杂度$O(m\sqrt{m}+m\log m)$
代码：
1 |
|