luogu_3645: 雅加达的摩天楼

雅加达的摩天楼

题意描述:

有\(N\)座摩天楼，从左到右依次编号为\(0\)到\(N-1\)。
有\(M\)个信息传递员，编号依次为\(0\)到\(M-1\)。编号为i的传递员最初在编号为\(B_i\)的摩天楼，邮递员可以在摩天楼之间跳跃(向前或者向后)，编号为\(i\)的传递员跳跃能力为\(P_i\)。
当传递员到达一个摩天楼他可以执行两种操作
- 1: 跳跃到其他摩天楼上。
- 2: 将消息传递给当前摩天楼的其他传递员。
最终要将编号为\(0\)的摩天楼信息传递到编号为\(1\)的摩天楼地方。

输入格式:

第一行输入\(N\)和\(M\)。\((1\leq n \leq 3*10^4,1\leq m \leq 3*10^4)\)
接下来第\(2\)到\(M+1\)，每行包含两个整数\(B_i\)和\(P_i\)。

输出格式:

输出一行，表示最小步数，如果无法到达则输出\(-1\)。

解题思路：

分析完题目后可以想到是最短路，对于每一个传递员都可以跳到别处，可以以此建立起点和终点，边权为1。
考虑暴力加边的做法，但是如果\(p\)很小的时候，最坏情况下有\(n^2\)条边，任何最短路算法都无法通过。
优化建图，采用分块的思想: 将\(n\)点合并为\(\sqrt{n}\)个块
- 对于\(P_i\leq\sqrt{n}\)的传递员：
  - 对于某一栋摩天大楼，就把他从一个点转化为一栋真的摩天大楼。
  - 对于每栋楼建\(\sqrt{n}\)层，每层有\(n\)个点，第一层代表\(p=1\)的走法，第二层代表\(p=2\)的走法,....。其中第\(0\)代表原先的那个点。
  - 然后暴力加边。第\(i\)层代表\(P=i\)的情况，间距为\(i\)的点相互连长度为\(1\)的边。再把这些辅助点全部连向底边。
- 对于每个\(P_i>\sqrt{n}\)的点向其能达到的所有点的第\(0\)层加边。
总边数不会超过\(N\sqrt{N}\)。
建图完毕，跑最短路。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = (3e4 + 10)*500;

const int maxm = (3e4 + 10)*500;

int n, m;

int s, t; //起点和终点

int B[maxn], P[maxn]; //起始于B, 跳跃能力为P

int block;

int head[maxn], nex[maxn<<1], ver[maxn<<1], edge[maxn<<1], tot;

inline void add_edge(int x, int y, int z)

{

    ver[++tot] = y; edge[tot] = z;

    nex[tot] = head[x]; head[x] = tot;

}

inline int get_block(int x, int y){

    return x*n + y;

}

int dist[maxn];

bool v[maxn];

void SPFA()

{

    memset(dist, 0x3f, sizeof(dist));

    dist[s] = 0; queue<int> q;

    q.push(s); v[s] = 1;

    while(q.size())

    {

        int x = q.front(); q.pop();

        v[x] = 0;

        for(int i = head[x]; i; i = nex[i])

        {

            int y = ver[i], z = edge[i];

            if(dist[y] > dist[x] + z)

            {

                dist[y] = dist[x] + z;

                if(!v[y])

                {

                    q.push(y);

                    v[y] = 1;

                }

            }

        }

    }

    printf("%d\n", dist[t] == 0x3f3f3f3f ? -1 : dist[t]);

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = 1, x, y; i <= m; i++)

    {

        scanf("%d%d", &x, &y);

        B[i] = x + 1, P[i] = y;

    }

    //起始位置 终止位置 块的大小

    s = B[1], t = B[2]; block = min((int)sqrt(n), 100);

    //每一个点转化为一栋楼, 有sqrt(n)层

    for(int i = 1; i <= block; i++)

        for(int j = 1; j <= n; j++)

    {

        add_edge(get_block(i, j), j, 0); //楼底到每一层连边

        if(j <= n - i) //j条一次跳出范围了

        {

            //每一层间隔为i的点 跳一次边权为1

            add_edge(get_block(i,j), get_block(i,j)+i, 1);

            add_edge(get_block(i,j)+i, get_block(i,j), 1);

        }

    }

    for(int i = 1; i <= m; i++) //考虑每一个doge的跳跃能力

    {

        // 对于每一个传递员, 从楼底到Pi层对应连边

        if(P[i] <= block)

            add_edge(B[i], get_block(P[i], B[i]), 0);

        else

        {   //如果大于一个块了 那就暴力加边 因为有sqrt个块 所以加sqrt条边

            for(int j = 1; B[i] + j * P[i] <= n; j++)

                add_edge(B[i], B[i] + j*P[i], j); //向前跳

            for(int j = 1; B[i] - j * P[i] >= 1; j++)

                add_edge(B[i], B[i] - j*P[i], j); //向后跳

        } //这里最大可能加N*sqrt(N)条边

    } SPFA(); //优化后边数有 N*sqrt(N)的规模

    return 0;

}

巴特西

luogu_3645: 雅加达的摩天楼

雅加达的摩天楼

题意描述:

输入格式:

输出格式:

解题思路：

代码：

最新文章

热门文章