BZOJ #4070 [Apio2015]雅加达的摩天楼

Description

印尼首都雅加达市有 $N$ 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 $0$ 到 $N−1$。除了这 $N$ 座摩天楼外,雅加达市没有其他摩天楼。

有 $M$ 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 $0$ 到 $M−1$。编号为 $i$ 的 doge 最初居住于编号为 $B_i$ 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 $i$ 的 doge 的跳跃能力为 $P_i$ ($P_i>0$)。

在一次跳跃中,位于摩天楼 $b$ 而跳跃能力为 $p$ 的 doge 可以跳跃到编号为 $b−p$ (如果 $0≤b−p<N$)或 $b+p$ (如果 $0≤b+p<N$)的摩天楼。

编号为 $0$ 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编 号为 $1$ 的 doge。任何一个收到消息的 doge 有以下两个选择:

  1. 跳跃到其他摩天楼上;
  2. 将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 $0$ 号 doge 传递到 $1$ 号 doge 所需要的最少总跳跃步数,或者告诉它们消息永远不可能传递到 $1$ 号 doge。

Solution

这道题建图非常妙,一道最短路题建图甚至比网络流还要精妙。

考虑暴力建图,对每个点 $i$ 都向其能到达的点 $j$ 连边,很显然最坏情况需要 $n^2$ 条边,会炸。

样例的暴力建图,边数相当可观

考虑换一种建边方式,对于每次能跳 $x$ 步的点 $i$,连接 “…、$(i,i-x)$、$(i,i+x)$、$(i+x,i+2x)$、$(i+2x,i+3x)$、… ” 这些边。

但是这个做法是错的,因为当你到达一个点的时候,你可能不是经由上一只可以跳 $x$ 步的 doge 过来的,这个点上的 doge 也不能跳 $x$ 步,所以再走 $x$ 步的这条边就错了。

解决办法是建虚点,对于每个点建立一层虚点,虚点之间用 $x$ 长度的边连接,每一层虚点相互独立。对应的主点向其连接长度为 $0$ 的单向边,每个虚点向每个同位置的主点连接长度为 $0$ 的单向边,这样,就确保了每只 doge 互不干扰。

如图,蓝色的是虚点,5~9 是 0 的虚点,10~14 是 1 的虚点,25~29 是 4 的虚点,点 0 到点 1 的最短路为 5

更进一步,虚点是可以重复利用的。一排虚点上,每个虚点都向左右离它 $x$ 个长度的点建边,这排虚点就可以给所有长度为 $x$ 的 doge 用,而不会冲突(在 $i$ 点只能跳到 $i+x$ 和 $i-x$ 两个点)。

这排虚点可以给所有跳跃长度为 2 的 doge 用

所以我们可以为每个跳跃长度的 doge 都建立一排虚点,像这样:

纵向的边被省略了

但是这样做有一个问题,如果 $n$ 大了点数还是要过多。

我们可以设定一个阈值 $k$,小于 $k$ 的就走虚边,大于 $k$ 的就直接在原来的点上连接所有能到达的点。所以我们只需要建 $k$ 层虚点,时间复杂度足够。

k 如何取值?一般来说我们喜欢令 $k=\sqrt n$,但在这道题里却不是最优的,所以这道题有 $k=min\{100,\sqrt n\}$ 这种操作($k$ 过大层数多反而没有直接暴力建边快)。

实际上,$k$ 的最佳取值是 $\sqrt {\frac13n}$,因为我太菜不会证,这里放一个洛谷题解的证明:

Source: https://www.luogu.com.cn/blog/wufeiyang/solution-p3645

这是样例的最终建图:

用 SPFA (Dijkstra 会 T) 跑一遍最短路即可。

注意有个坑,是 $0$ 号 $doge$ 到 $1$ 号 $doge$,而不是 $0$ 号楼到 $1$ 号楼。

应该是最近写的最走心的博文了。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int n,m;
int head[3100000],top=0,d[3100000];
bool v[3100000]; 
struct node{
    int v,w,next;
}s[18000005];
void add(int a,int b,int c){
    s[top].v=b;
    s[top].w=c;
    s[top].next=head[a];
    head[a]=top++;
}
void spfa(int x,int maxn){
    queue<int> q;
    for(int i=0;i<=maxn;i++){
        d[i]=214748364;
        v[i]=false;
    }
    d[x]=0;
    q.push(x);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        v[now]=false;
        for(int i=head[now];i!=-1;i=s[i].next){
            int to=s[i].v;             
            if(d[to]==214748364||d[to]>d[now]+s[i].w){
                d[to]=d[now]+s[i].w;
                if(!v[to]){
                    v[to]=true;
                    q.push(to);
                }
            }
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    int siz=min(int(sqrt(n)),100);
    for (int i=1;i<=siz;i++){
    	for (int j=0;j<=n-1;j++){
    		if (i+j>=n){
    			break;
			}
    		add(i*n+j,i*n+j+i,1);
    		add(i*n+j+i,i*n+j,1);
		}
    	for (int j=0;j<=n-1;j++){
    		add(i*n+j,j,0);
		}
	}
    int S,T;
    for (int i=1;i<=m;i++){
    	int x=read(),y=read();
    	if (i==1){
    		S=x;
		}
		if (i==2){
			T=x;
		}
    	if (y>siz){
    		for (int j=x-y,k=1;j>=1;j-=y,k++){
    			add(x,j,k);
			}
			for (int j=x+y,k=1;j<=n-1;j+=y,k++){
				add(x,j,k);
			}
		}else{
			add(x,y*n+x,0);
		}
	}
	spfa(S,(siz+1)*n);
	if (d[T]>=214748364){
		d[T]=-1;
	}
    cout<<d[T];
    return 0;
}
BZOJ建图最短路

评论

  1. 卓卓
    Windows Chrome
    2月前
    2020-9-04 21:50:29

    这个代码块是怎么做的?

    • solstice23 博主
      Android Chrome
      2月前
      2020-9-05 12:08:44

      直接插入代码块,再在 Argon 设置里开启 Highlight.js 选项

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇
下一篇