[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]);

	}

}

巴特西

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

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

题面

分析

代码

最新文章

热门文章