锐客网

  1. 首页 > it技术 > >

数据结构|[codeforces 938G]Shortest Path Queries

数据结构并查集

题目大意
给定一个n个点m条边的无向联通简单图，边有边权。接下来有q次操作，操作有三种：
1. 添加一条边，保证添加后仍是简单图
2. 删除一条边，保证删除后仍是联通图
3. 给定x,y，求所有x到y的路径中所有边权异或和最小值（一条边经过多次算多次）
n,m,q≤200000
边权 <230
分析
首先我们联想到CF另一道题845G，这题没有前两个操作，只询问1到n的答案。
那道题的解法是随便拿出一个生成树，设f[x]表示x到根简单路径的异或和，x到y的树上简单路径可以表示成f[x]^f[y]。
对于非树边，它可以得到一个环。走一次环的异或和可以通过上面方法得到。我们把每个环的异或值都加进线性基里，表示每个环都可以走。环相交、走重边等情况容易发现边权会抵消掉，所以答案就是f[1]^f[n]和任意个环异或得到的最小值。用线性基可以log的时间出解。
【数据结构|[codeforces 938G]Shortest Path Queries】回到此题，一个思路就是：对于所有边，记录它的出现时间区间，然后对于时间开个线段树，把边存在里面。显然一条边最多被分成log条。然后遍历这个线段树，对于一个询问，此时的图就是线段树上该叶子到根路径上所有边组成的。
我们可以用并查集维护连通性，同时维护上面提到的f[]数组（注意这里回溯时会有撤销操作，要按秩合并）。线性基可以每递归下一层复制一遍。
那么时间复杂度是 O(nlog2n) 的

#include #include #include #include #define fi first #define se second #define mkp make_pairusing namespace std; const int N=4e5+5,M=N*20,Log=30,T=524295; typedef long long LL; typedef pair PII; int n,m,q,tot,f[Log][Log],h[T],E[N][5],cnt,e[M],nxt[M],Ask,Q[N][2],Rank[N],sum[22],pr[22][N],pId[22][N]; PII dsu[N],P[22][N]; map H; char c; int read() { int x=0,sig=1; for (c=getchar(); c<'0' || c>'9'; c=getchar()) if (c=='-') sig=-1; for (; c>='0' && c<='9'; c=getchar()) x=x*10+c-48; return x*sig; }void Add(int x,int y) { e[++tot]=y; nxt[tot]=h[x]; h[x]=tot; }void Ins(int l,int r,int a,int b,int v,int x) { if (l==a && r==b) { Add(x,v); return; } int mid=l+r>>1; if (b<=mid) Ins(l,mid,a,b,v,x<<1); else if (a>mid) Ins(mid+1,r,a,b,v,x<<1|1); else { Ins(l,mid,a,mid,v,x<<1); Ins(mid+1,r,mid+1,b,v,x<<1|1); } }PII Get(int x) { int t=0; for (; dsu[x].fi!=x; x=dsu[x].fi) t^=dsu[x].se; return mkp(x,t); }void Add_Loop(int x,int dep) { for (int i=Log-1; i>=0; i--) if (((1<0) { if (!f[dep][i]) { f[dep][i]=x; break; } x^=f[dep][i]; } }int getmin(int x,int dep) { for (int i=Log-1; i>=0; i--) if (((1<0) x^=f[dep][i]; return x; }void solve(int l,int r,int x,int dep) { for (int i=0; iRank[q.fi]) swap(p,q); P[dep][++sum[dep]]=dsu[p.fi]; pr[dep][sum[dep]]=Rank[p.fi]; pId[dep][sum[dep]]=p.fi; P[dep][++sum[dep]]=dsu[q.fi]; pr[dep][sum[dep]]=Rank[q.fi]; pId[dep][sum[dep]]=q.fi; dsu[p.fi].fi=q.fi; dsu[p.fi].se=p.se ^ q.se ^ E[e[i]][2]; if (Rank[p.fi]==Rank[q.fi]) Rank[q.fi]++; } } if (l==r) { p=Get(Q[l][0]); q=Get(Q[l][1]); printf("%d\n",getmin(p.se ^ q.se,dep)); }else { int mid=l+r>>1; solve(l,mid,x<<1,dep+1); solve(mid+1,r,x<<1|1,dep+1); } for (int i=sum[dep]; i; i--) { int j=pId[dep][i]; dsu[j]=P[dep][i]; Rank[j]=pr[dep][i]; } }int main() { n=read(); m=read(); for (int i=1; i<=m; i++) { E[i][0]=read(); E[i][1]=read(); E[i][2]=read(); if (E[i][0]>E[i][1]) swap(E[i][0],E[i][1]); H[(LL)E[i][0]*(n+1)+E[i][1]]=i; E[i][3]=1; } for (q=read(); q--; ) { int typ=read(); if (typ==1) { E[++m][0]=read(); E[m][1]=read(); E[m][2]=read(); if (E[m][0]>E[m][1]) swap(E[m][0],E[m][1]); H[(LL)E[m][0]*(n+1)+E[m][1]]=m; E[m][3]=Ask+1; }else if (typ==2) { int x=read(),y=read(); if (x>y) swap(x,y); int i=H[(LL)x*(n+1)+y]; H[(LL)x*(n+1)+y]=0; E[i][4]=Ask; }else { Q[++Ask][0]=read(); Q[Ask][1]=read(); } } for (int i=1; i<=m; i++) { if (H[(LL)E[i][0]*(n+1)+E[i][1]]==i) E[i][4]=Ask; if (E[i][3]<=E[i][4]) Ins(1,Ask,E[i][3],E[i][4],i,1); } tot=0; for (int i=1; i<=n; i++) dsu[i]=mkp(i,0),Rank[i]=0; solve(1,Ask,1,1); return 0; }

    推荐阅读


    上一篇：2018年4月20号

    下一篇：容斥原理|【WC2017模拟1.22】简单题