题目来源：Hnoi2016Day1T1/BZOJ4537
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
5
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
解题思路
“路径可以不是简单路径”即“路径”实际上对应的是一个联通块。原问题等价于找到一个包含u和v的联通块，使得这个联通块内a的最大值等于一个给定的值，且b的最大值等于一个给定的值。
考虑只有一个询问的情况，我们按照a从小到大枚举边，如果b小于等于给定的值那么连上这条边。最后判连通性即可。时间复杂度O(m*alpha)。
对于所有询问，首先按照a从小到大排序，这样每次对应的就是从头开始的连续一段边（可能）有用。但是由于b的限制，不是所有边都可以加。看起来不太可以用数据结构维护。考虑将b分块。按照阈值(i*sqrt(m))（以边的编号为值）维护块数个情况。这样对于每次询问只有O(sqrt(m))的信息是缺失的。只需要每次询问时加入然后暴力撤销就可以了。每次维护的时间复杂度O(sqrt(m)),每次询问的时间复杂度O(sqrt(m)*alpha)。所以总时间复杂度为O(m*sqrt(m)*alpha)。
注：alpha这里表示并查集的复杂度。
代码
/************************************************************** Problem: 4537 User: VictBr Language: C++ Result: Accepted Time:15644 ms Memory:321340 kb ****************************************************************/ #include <bits/stdc++.h> /* 1当前已加入的在最后一个可能成为答案的块中不是所有边的b都小于目标b，所以要判断。 2由于用b重新算下标，询问应该在加边之后，所以排序时要把加边排前面。 3当询问在第一块时，调用到第0块的值，所以第0块要赋初值。 4gg处u打成v 5aa处由于询问可能在第一块，now可能是0，所以要赋初值。 */ using namespace std; const int N = 50010; void read(int &x){ char ch = getchar(); while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0',ch = getchar(); } struct Node{ int u,v,a,b,id; Node(){} Node(int u,int v,int a,int b,int id):u(u),v(v),a(a),b(b),id(id){} }nod[N<<2],edge[N<<1]; struct Point{ int fa,a,b,siz; Point(){} Point(int fa,int a,int b,int siz):fa(fa),a(a),b(b),siz(siz){} }pt[N][400]; struct Stack{ Point p;int x; Stack(){} Stack(Point p,int x):p(p),x(x){} }sta[N]; int lent[400]; int n,m,q,K,len,rk[N<<1],rk2[N]; int tt; //rk edge rk2 ques bool ans[N]; bool cmp1(const Node &x,const Node &y){return x.a < y.a;} bool cmp2(const Node &x,const Node &y){ return x.b == y.b ? x.id < y.id : x.b < y.b; } bool cmp3(const Node &x,const Node &y){ return x.a == y.a ? (x.b == y.b ? x.id < y.id : x.b < y.b) : x.a < y.a; } int getfa(int x,int y){ if (pt[x][y].fa == x) return x; pt[x][y].fa = getfa(pt[x][y].fa,y); return pt[x][y].fa; } int getfa2(int x,int y){ if (pt[x][y].fa == x) return x; return getfa2(pt[x][y].fa,y); } int main(){ read(n);read(m);K = sqrt(m); for (int i = 1;i <= m;i++){ int u = 0,v = 0,a = 0,b = 0; read(u);read(v);read(a);read(b); nod[++len] = Node(u,v,a,b,-i); } read(q); for (int i = 1;i <= q;i++){ int u = 0,v = 0,a = 0,b = 0; read(u);read(v);read(a);read(b); nod[++len] = Node(u,v,a,b,i); } sort(nod+1,nod+1+len,cmp1); int cnt = 1; for (int i = 2;i <= len;i++) if (nod[i].a == nod[i-1].a) nod[i-1].a = cnt; else nod[i-1].a = cnt++; nod[len].a = cnt; sort(nod+1,nod+1+len,cmp2); cnt = 1; for (int i = 2;i <= len;i++){ if (nod[i].b == nod[i-1].b) nod[i-1].b = cnt; else nod[i-1].b = cnt++; } nod[len].b = cnt; cnt = 0; for (int i = 1;i <= len;i++) if (nod[i].id < 0) { rk[-nod[i].id] = ++cnt; } else rk2[nod[i].id] = cnt; sort(nod+1,nod+1+len,cmp3); cnt = 0; for (int j = K;j-K < m;j += K) cnt++; for (int i = 1;i <= n;i++) for (int j = 0;j <= cnt;j++) pt[i][j] = Point(i,0,0,1); for (int i = 1;i <= len;i++){ if (nod[i].id < 0){ int num = -nod[i].id;bool used = 0; for (int j = K,tot = 1;j-K < m;j += K,tot++){ if (rk[num] <= j){ if (!used){ used = 1; lent[tot]++; edge[j-K+lent[tot]] = nod[i]; } int u = nod[i].u,v = nod[i].v; getfa(u,tot); getfa(v,tot); int x = pt[v][tot].fa,y = pt[u][tot].fa; if (x != y){ if (pt[x][tot].siz < pt[y][tot].siz) swap(x,y); pt[y][tot].fa = x; pt[x][tot].a = max(max(pt[x][tot].a,pt[y][tot].a),nod[i].a); pt[x][tot].b = max(max(pt[x][tot].b,pt[y][tot].b),nod[i].b); pt[x][tot].siz += pt[y][tot].siz; } else{ pt[x][tot].a = max(pt[x][tot].a,nod[i].a); pt[x][tot].b = max(pt[x][tot].b,nod[i].b); } } } } else{ tt = 0; int num = nod[i].id,now = 0;/*aa*/ for (int j = K,tot = 1;j < rk2[num];j += K,tot++) now = tot; for (int j = 1;j <= lent[now+1];j++){ int where = K*now+j; if (edge[where].b > nod[i].b) continue; int u = edge[where].u,v = edge[where].v; u = getfa2(u,now); v = getfa2(v,now); if (u != v){ if (pt[u][now].siz > pt[v][now].siz) swap(u,v); sta[++tt] = Stack(pt[u][now],u); sta[++tt] = Stack(pt[v][now],v); pt[u][now].fa = v; pt[v][now].siz += pt[u][now].siz; pt[v][now].a = max(max(pt[v][now].a,pt[u][now].a),edge[where].a); pt[v][now].b = max(max(pt[v][now].b,pt[u/*gg*/][now].b),edge[where].b); } else{ sta[++tt] = Stack(pt[v][now],v); pt[v][now].a = max(pt[v][now].a,edge[where].a); pt[v][now].b = max(pt[v][now].b,edge[where].b); } } int u = nod[i].u,v = nod[i].v; u = getfa2(u,now); v = getfa2(v,now); if (u == v && nod[i].a == pt[u][now].a && nod[i].b == pt[u][now].b) ans[num] = 1; for (int j = tt ;j >= 1;j--) pt[sta[j].x][now] = sta[j].p; } } for (int i = 1;i <= q;i++) if (ans[i]) printf("Yes "); else printf("No "); return 0; }
后记
拖了半个多月，终于把这坑补上了。主要原因是这周作业比较少，其他事也比较少。