北京上地网站建设,深圳网站建设汤小巧,聚名网官方,广州做网页的公司4537: [Hnoi2016]最小公倍数 Time Limit: 40 Sec Memory Limit: 512 MBSubmit: 1474 Solved: 521[Submit][Status][Discuss]Description 给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)#xff0c;每条边上带有权值。所有权值都可以分解成2^a*3^b的形式。现在有q个询问每条边上带有权值。所有权值都可以分解成2^a*3^b的形式。现在有q个询问每次询问给定四个参数u、v、a和b请你求出是否存在一条顶点u到v之间的路径使得路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意路径可以不是简单路径。下面是一些可能有用的定义最小公倍数K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。路径路径P:P1,P2,…,Pk是顶点序列满足对于任意1ik节点Pi和Pi1之间都有边相连。简单路径如果路径P:P1,P2,…,Pk中对于任意1s≠tk都有Ps≠Pt那么称路径为简单路径。 Input 输入文件的第一行包含两个整数N和M分别代表图的顶点数和边数。接下来M行每行包含四个整数u、v、a、b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q代表询问数。接下来q行每行包含四个整数u、v、a和b代表一次询问。询问内容请参见问题描述。1n,q50000、1m100000、0a,b10^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 HINT Source 考虑暴力做法对于每一个询问暴力加入满足询问的边然后维护联通性和maxpmaxqmaxpmaxq如果满足条件则YesYes。 两个条件的限制似乎很难用别的数据结构优化掉那么考虑分块先以pp为第一关键字qq为第二关键字排序每$m^{0.5}$分成一块。然后把每一个询问归类到相应的块中使得这个询问的$p$大于等于块的$p$最小值小于等于最大值。 依次扫每个块把每个块的询问取出来。设当前的块号是$i$,那么我们把$1$到$i-1$的块里面的所有的边按$b$排序 再把这个块内的询问按$q$排序。然后扫$1$到$i-1$的符合当前询问的边加入并查集。对于i块内的边只能暴力扫然后加入并查集了注意处理完这个询问后要撤销掉在该块内加入的边。 所以此题的并查集不能路径压缩要用启发式合并或按秩合并两者都是$logn$的总的时间复杂度时$O(n^{1.5}logn)$。 将代码中的启发式换成按秩合并可AC否则TLE 1 #includeiostream2 #includecstring3 #includecstdlib4 #includecstdio5 #includecmath6 #includealgorithm7 #define ll long long8 #define maxn 1401059 using namespace std;
10 int read() {
11 int x0,f1;char chgetchar();
12 for(;!isdigit(ch);chgetchar()) if(ch-) f-1;
13 for(;isdigit(ch);chgetchar()) xx*10ch-0;
14 return x*f;
15 }
16 int n,m,k;
17 struct data {
18 int a,b,p,q,id,f;
19 bool operator (const data tmp) const{
20 return ptmp.p?qtmp.q:ptmp.p;
21 }
22 }e[maxn],ask[maxn],tmp[maxn],sta[maxn];
23 int fa[maxn],sz,ma[maxn],mb[maxn],size[maxn];
24 int ans[maxn];
25 int find(int x) {return fa[x]x?fa[x]:find(fa[x]);}
26 int cnt0;
27 void merge(int x,int y,int a,int b) {
28 xfind(x),yfind(y);
29 if(size[x]size[y]) swap(x,y);
30 sta[cnt].ax;sta[cnt].by;sta[cnt].pma[y];sta[cnt].qmb[y];sta[cnt].ffa[x];sta[cnt].idsize[y];
31 if(xy) {
32 ma[x]max(ma[x],a);
33 mb[x]max(mb[x],b);
34 }
35 else {
36 fa[x]y;
37 size[y]size[x];
38 ma[y]max(ma[y],a);
39 mb[y]max(mb[y],b);
40 ma[y]max(ma[x],ma[y]);
41 mb[y]max(mb[x],mb[y]);
42 }
43 }
44 bool cmp(data a,data b) {return a.qb.q?a.pb.p:a.qb.q;}
45 int main() {
46
47 nread(),mread();
48 for(int i1;im;i) {
49 e[i].aread();e[i].bread();e[i].pread();e[i].qread();
50 }
51 sort(e1,em1);
52 szsqrt(m);
53 kread();
54 for(int i1;ik;i) {
55 ask[i].aread(),ask[i].bread(),ask[i].pread(),ask[i].qread();ask[i].idi;
56 }
57 sort(ask1,askk1,cmp);
58 for(int i1;im;isz) {
59 int top0;
60 for(int j1;jk;j) if(ask[j].pe[i].p(iszm||ask[j].pe[isz].p)) tmp[top]ask[j];
61 sort(e1,ei,cmp);
62 for(int j1;jn;j) fa[j]j,size[j]1,ma[j]mb[j]-2147483647;
63 int w1;
64 for(int j1;jtop;j) {
65 for(;wi;w) {
66 if(e[w].qtmp[j].q) break;
67 merge(e[w].a,e[w].b,e[w].p,e[w].q);
68 }
69 cnt0;
70 for(int ti;tisz;t) {
71 if(e[t].ptmp[j].pe[t].qtmp[j].q) merge(e[t].a,e[t].b,e[t].p,e[t].q);
72 }
73 int t1find(tmp[j].a),t2find(tmp[j].b);
74 if(t1t2ma[t1]tmp[j].pmb[t1]tmp[j].q) ans[tmp[j].id]1;
75 while(cnt) {
76 fa[sta[cnt].a]sta[cnt].f;
77 ma[sta[cnt].b]sta[cnt].p;
78 mb[sta[cnt].b]sta[cnt].q;
79 size[sta[cnt].b]sta[cnt].id;
80 cnt--;
81 }
82 }
83 }
84 for(int i1;ik;i) if(ans[i]) puts(Yes);else puts(No);
85
86 } View Code 转载于:https://www.cnblogs.com/wls001/p/8435071.html
