首页 > 代码库 > 【bzoj3073】[Pa2011]Journeys 线段树优化建图+堆优化Dijkstra
【bzoj3073】[Pa2011]Journeys 线段树优化建图+堆优化Dijkstra
题目描述
Seter建造了一个很大的星球，他准备建造N个国家和无数双向道路。N个国家很快建造好了，用1..N编号，但是他发现道路实在太多了，他要一条条建简直是不可能的！于是他以如下方式建造道路：(a,b),(c,d)表示，对于任意两个国家x,y，如果a<=x<=b,c<=y<=d，那么在xy之间建造一条道路。Seter保证不会有一个国家与自己之间有道路。
Seter好不容易建好了所有道路，他现在在位于P号的首都。Seter想知道P号国家到任意一个国家最少需要经过几条道路。当然，Seter保证P号国家能到任意一个国家。
注意：可能有重边
输入
第一行三个数N,M,P。N<=500000,M<=100000。
后M行，每行4个数A，B，C，D。1<=A<=B<=N,1<=C<=D<=N。
输出
N行，第i行表示P号国家到第i个国家最少需要经过几条路。显然第P行应该是0。
样例输入
5 3 4
1 2 4 5
5 5 4 4
1 1 3 3
样例输出
1
1
2
0
1
题解
线段树优化建图+堆优化Dijkstra
看别人blog看到了这道题，于是决定YY一发。
一个朴素（已经不是最朴素的了）的加边方法：a~b的所有点->p1，长度为0；p1->p2，长度为1；p2->c~d的所有点，长度为0，其中加的都是有向边，p1和p2是新建的两个辅助点，然后再反过来进行这个过程。
然而这样加边的话边数依旧巨大。
由于给出的加边都是区间形式，所以我们可以用维护区间的数据结构——线段树，去优化这个建图过程。
具体方法（这里只讲加有向边a~b->c~d的方法）：
建立两颗线段树A、B，其中A线段树每个非叶子节点的儿子向该节点连边，长度为0，B线段树每个非叶子节点向该节点的儿子连边，长度为0；B线段树的叶子结点向A线段树对应的叶子结点连边，长度为0。
这里面A线段树的叶子结点代表原图中的节点，其余节点都是用来优化建图。
对于加边操作，找到A线段树上a~b对应的区间节点，这些节点向p1连边，长度为0；p1->p2，长度为1；找到B线段树上c~d对应的区间节点，p2向这些节点连边，长度为0.
最后跑堆优化Dijkstra出解。
应该不是很难理解，具体可以见代码。
#include <cstdio>#include <cstring>#include <queue>#include <utility>#define N 500010#define M 3500010using namespace std;priority_queue<pair<int , int> > q;int head[M] , to[M << 3] , len[M << 3] , next[M << 3] , cnt , ls[N << 3] , rs[N << 3] , ra , rb , tot , v[N] , n , dis[M] , vis[M];void add(int x , int y , int z){ to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}void build(int l , int r , int &x , int flag){ x = ++tot; if(l == r) { if(flag) v[l] = x; return; } int mid = (l + r) >> 1; build(l , mid , ls[x] , flag) , build(mid + 1 , r , rs[x] , flag); if(flag) add(ls[x] , x , 0) , add(rs[x] , x , 0); else add(x , ls[x] , 0) , add(x , rs[x] , 0);}void deal(int l , int r , int x , int y){ if(l == r) { add(y , x , 0); return; } int mid = (l + r) >> 1; deal(l , mid , ls[x] , ls[y]) , deal(mid + 1 , r , rs[x] , rs[y]);}void update(int b , int e , int p , int l , int r , int x , int flag){ if(b <= l && r <= e) { if(flag) add(x , p , 0); else add(p , x , 0); return; } int mid = (l + r) >> 1; if(b <= mid) update(b , e , p , l , mid , ls[x] , flag); if(e > mid) update(b , e , p , mid + 1 , r , rs[x] , flag);}void link(int a , int b , int c , int d){ update(a , b , ++tot , 1 , n , ra , 1) , add(tot , tot + 1 , 1) , update(c , d , ++tot , 1 , n , rb , 0);}int main(){ int m , p , a , b , c , d , i , x; scanf("%d%d%d" , &n , &m , &p); build(1 , n , ra , 1) , build(1 , n , rb , 0) , deal(1 , n , ra , rb); for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d%d" , &a , &b , &c , &d) , link(a , b , c , d) , link(c , d , a , b); memset(dis , 0x3f , sizeof(dis)) , dis[v[p]] = 0 , q.push(make_pair(0 , v[p])); while(!q.empty()) { x = q.top().second , q.pop(); if(vis[x]) continue; vis[x] = 1; for(i = head[x] ; i ; i = next[i]) if(dis[to[i]] > dis[x] + len[i]) dis[to[i]] = dis[x] + len[i] , q.push(make_pair(-dis[to[i]] , to[i])); } for(i = 1 ; i <= n ; i ++ ) printf("%d\n" , dis[v[i]]); return 0;}
【bzoj3073】[Pa2011]Journeys 线段树优化建图+堆优化Dijkstra
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。