「笔记」01bfs 学习笔记 & CF1601B 题解

主要用途：用来解决边权只有 \(0\) 或 \(1\) 的最短路问题。或者能够转化为这种边权值的最短路问题。

主要方法：用一个双端队列 deque，被边权为 \(0\) 的边更新的点放到队首，被边权为 \(1\) 的边更新的点放到队尾。

时间复杂度 \(\mathcal O(n+m)\)。避免使用其他最短路算法造成的时间浪费。

正确性：因为只有 \(0,1\)，这样入队在队列中的点 \(v\) 仍然具有单调性（是指 \(dis_v\) 的单调性）。

以 CF1601B Frog Traveler 为例

考虑再建立 \(n+1\) 个虚点分别对应 \([0,n]\)。

对于一个 \(a_i\) 就是 \(i\) 的实点向 \([i, i - a_i]\) 的虚点连一条边权为 \(1\) 的边。这一部分可以使用线段树优化建图（具体题目参照 CF786B）。

对于一个 \(b_i\) 就是 \(i\) 的虚点向 \(i + b_i\) 的实点连一条边权为 \(0\) 的边。

然后用 01bfs 跑最短路即可，记得记录路径。

Code：

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"<> 1; id[i] = ++ Cnt;
        Build(lson, l, mid), Build(rson, mid + 1, r);
        if(id[lson]) add_edge(id[i], id[lson], 0);
        if(id[rson]) add_edge(id[i], id[rson], 0);
    }
    void Modify(int i, int l, int r, int L, int R, int u) {
        if(L <= l && r <= R) return add_edge(u, id[i], 1);
        int mid = (l + r) >> 1;
        if(mid >= L) Modify(lson, l, mid, L, R, u);
        if(mid < R) Modify(rson, mid + 1, r, L, R, u);
    }
}

void bfs() {
    deque q;
    dis[n] = 0, q.push_back(n);
    while(!q.empty()) {
        int u = q.front(); q.pop_front();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if(dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) {
                    pre[v] = u;
                    if(e[i].w) q.push_back(v);
                    else q.push_front(v);
                }
            }
        }
    }
}

void Print(int u) {
    if(pre[u] != n) Print(pre[u]);
    if(n + 1 <= u && u <= 2 * n + 1) printf("%d ", u - n - 1);
}

int main()
{
	n = read(); Cnt = 2 * n + 1;
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 1; i <= n; ++i) b[i] = read();
    for(int i = 0; i <= n; ++i) add_edge(i + n + 1, i + b[i], 0);
	Seg::Build(1, 0, n);
	for(int i = 1; i <= n; ++i) Seg::Modify(1, 0, n, i - a[i], i, i);
    memset(dis, 0x3f, sizeof dis);
    bfs();
    if(dis[0] == 0x3f3f3f3f) puts("-1");
    else {
        printf("%d\n", dis[0]);
        Print(0);
    }
    return 0;
}

这里多说一句，这个题的另一个做法：

@摸鱼酱：
考虑 bfs，每个点 \(y\) 被跳上来，下滑 \(b_y\) 米之前第一次到达就是最优的，所以每个点只会被搜到一次。
这样我们就可以把 \([0,n-1]\) 塞进 set，每次把 \([u-a_i,u]\) 中还没被访问过的点拉出来更新并放入下滑后的点入队列，然后把它们删除掉，每个点只会贡献一次删除和入队，时间复杂度 \(\mathcal O(n \log n)\)

Code：

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< S;
queue q;
vector ans;

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

void Print(int u) {
    if(pre[u] != n) Print(pre[u]);
    printf("%d ", u - add[u]);
}

int main()
{
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 1; i <= n; ++i) b[i] = read();
	for(int i = 0; i < n; ++i) S.insert(i);
	dis[n] = 1, q.push(n);
	while(!q.empty()) {
	    int u = q.front(); q.pop();
	    set::iterator l = S.lower_bound(u - a[u]), r = S.upper_bound(u);
	    for(set::iterator it = l; it != r; ++it) {
	        int v = *it;
	        if(!dis[v + b[v]]) {
	            dis[v + b[v]] = dis[u] + 1;
	            q.push(v + b[v]);
	            add[v + b[v]] = b[v];
	            pre[v + b[v]] = u;
            }
        }
        S.erase(l, r);
    }
    if(!dis[0]) puts("-1");
    else {
        printf("%d\n", dis[0] - 1);
//        Print(0);
        int u = 0;
        while(u != n) ans.push_back(u), u = pre[u];
        reverse(ans.begin(), ans.end());
        for(int v : ans) printf("%d ", v - add[v]);
        puts("");
    }
    return 0;
}