[Codeforces 464E] The Classic Problem（可持久化线段树）

喜欢ヅ旅行 2021-12-01 18:00 297阅读 0赞

## \[Codeforces 464E\] The Classic Problem（可持久化线段树） ##

### 题面 ###

给出一个带权无向图，每条边的边权是\\(2^\{x\_i\}(x\_i<10^5)\\)，求s到t的最短路\\(\\mathrm\{mod\} \\ 10^9+7\\)的值

### 分析 ###

显然边权存不下，由于取模会影响大小关系，不能直接取模然后跑dijkstra

考虑用可持久化线段树维护每个点到起点的距离(二进制表示)，即维护一个01序列,\[1,n\]从低位到高位存储。

修改的时候我们要把第i位+1，如果第i位是0，直接取反就可以了。但是第i位是1的时候不仅要取反，还要进位。这里可以直接暴力把连续的一段0改成1。理论上会被卡但这题的数据比较水，不被卡的做法参考cf官方题解

另外dijkstra算法中需要比较dist值大小，从高到低比较二进制的每一位。可以维护区间hash值，查询的时候在线段树上二分。如果右区间\[mid+1,r\]的hash值相同，就递归比较\[l,mid\],否则比较\[mid+1,r\].

具体见代码

### 代码 ###

//http://codeforces.com/problemset/problem/464/E #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #define maxn 500000 #define maxm 500000 #define maxlog 25 #define mod 1000000007 #define INF 0x3f3f3f3f using namespace std; int n,m,dg;//dg是二进制位数 long long pow2[maxn+5]; struct segment_tree{//主席树维护二进值位 ,下标[1,n]从低位到高位存储二进制 #define lson(x) tree[x].ls #define rson(x) tree[x].rs struct node{ int ls; int rs; long long sum;//二进制值取模mod之后的值 //既可以用来更新答案，也可以当做hash判断两端二进制是否相等 }tree[maxn*maxlog+5]; int ptr; void push_up(int x,int l,int r){ int mid=(l+r)>>1; tree[x].sum=tree[lson(x)].sum+tree[rson(x)].sum*pow2[mid-l+1]%mod; tree[x].sum%=mod; } int insert(int &x,int last,int upos,int l,int r){ x=++ptr; tree[x]=tree[last]; if(l==r){ tree[x].sum^=1;//+1，1变0，0变1，进位等下再处理 return tree[last].sum; } int mid=(l+r)>>1; int res; if(upos<=mid){ //upos<=mid,处理进位，[mid+1,r]对应的高位也会被进位，所以要递归下去修改 //考虑极端情况，xi都=1，那么需要进位O(m/2+m/4+m/8+...+1)≈O(m) res=insert(tree[x].ls,tree[last].ls,upos,l,mid); //如果res不等于0，说明之前[l,mid]就有值，要继续进位 if(res) res=insert(tree[x].rs,tree[last].rs,upos,mid+1,r); }else{ res=insert(tree[x].rs,tree[last].rs,upos,mid+1,r); } push_up(x,l,r); return res; } bool cmp(int x,int y,int l,int r){//比较x,y两棵主席树对应的二进制大小 if(l==r){ return tree[x].sum<tree[y].sum; } int mid=(l+r)>>1; if(tree[tree[x].rs].sum==tree[tree[y].rs].sum) return cmp(tree[x].ls,tree[y].ls,l,mid);//从高位到低位，高位相同就比低位 else return cmp(tree[x].rs,tree[y].rs,mid+1,r); } #undef lson #undef rson }T; struct edge{ int from; int to; int next; int len; }E[maxm*2+5]; int head[maxn+5]; int ecnt=1; void add_edge(int u,int v,int w){ ecnt++; E[ecnt].from=u; E[ecnt].to=v; E[ecnt].len=w; E[ecnt].next=head[u]; head[u]=ecnt; } struct heap_node{ int id; int rt;//对应二进制主席树的树根 heap_node(){ } heap_node(int _id,int _rt){ id=_id; rt=_rt; } friend bool operator < (heap_node p,heap_node q){ return !T.cmp(p.rt,q.rt,0,dg); } }; priority_queue<heap_node>q; int vis[maxn+5]; int disrt[maxn+5]; int pre[maxn+5]; long long dijkstra(int s,int t){ memset(disrt,0x3f,sizeof(disrt)); disrt[s]=0; q.push(heap_node(s,disrt[s])); while(!q.empty()){ heap_node x=q.top(); q.pop(); if(vis[x.id]) continue; vis[x.id]=1; for(int i=head[x.id];i;i=E[i].next){ int y=E[i].to; int tmprt; T.insert(tmprt,disrt[x.id],E[i].len,0,dg); if(disrt[y]==INF||T.cmp(tmprt,disrt[y],0,dg)){ disrt[y]=tmprt; pre[y]=i; q.push(heap_node(y,disrt[y])); } } } if(disrt[t]==INF) return -1; else return T.tree[disrt[t]].sum; } int cnt=0; int res[maxn+5]; void get_ans(int s,int t){ int x=t; while(x!=s){ res[++cnt]=x; x=E[pre[x]].from; } res[++cnt]=x; } int main(){ int u,v,w; int s,t; scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d %d %d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,w); dg=max(dg,w); } scanf("%d %d",&s,&t); dg+=log2(m)+1;//进位 pow2[0]=1; for(int i=1;i<=dg;i++) pow2[i]=pow2[i-1]*2%mod; long long ans=dijkstra(s,t); printf("%I64d\n",ans); if(ans==-1) return 0; cnt=0; get_ans(s,t); printf("%d\n",cnt); for(int i=cnt;i>=1;i--){ printf("%d ",res[i]); } }

转载于:https://www.cnblogs.com/birchtree/p/11185533.html