lyd读书笔记 宽搜(2)宽搜变形

双向宽搜

Meet in the middle,从两边同时开始,可以大量减少枚举次数。

HDU3085 NightMareII

末世主义轮回大作,讲述了世界尽头的两个男孩和女孩相遇的故事(不)

朴素的双向宽搜即可。

双端队列宽搜

一般的宽搜我们维护的其实是一张边权为1的图,或者至少是边权相等的。如果边权有所变化,一般宽搜不再适用。

对于边权为0或1的宽搜,我们采用双端队列宽搜。

电路维修

考虑对于格点$(x_1, y_1)$与$(x_2, y_2)$,两点之间的最短距离就是旋转的次数。现在我们发现,对于处在一个格点的对角线的格点来说,边权是0或1中的一个。

然后下面的那番话是啥意思。。我来大概翻译一下

考虑到,我们BFS的基础是队列中的各个元素是等权值的。换言之,对于权为定值的图来说,其拓展的过程中队列会分为两个完全相等的部分:前半部分是尚未拓展的点,这些点的权值为$x$;后半部分是拓展完成的点,这些点的权值为$x + 1$。这就是所谓的“两段性”。

现在对于边权为0和1的问题来说,我们为了保证这样的性质,应当将边权为0的放在前面,边权为1的放在后面。这样两段性就随之满足,这就是个合格的队列。

优先队列宽搜

本质

我们知道,一般的宽搜是具有“两段性的”,也就是,我们一定能将队列分且仅分成两段不同部分。

但是对于权值不同的状态,显然这种两段性是不使用的。那么就有两种解决方案。

一种是我们取消了进出队一次的限制,而可以随意更新。这样的话,无数次的松弛一定能够得到答案,在随机数据下表现非常出色但复杂度最坏情况下会退化为$O(n^2)$。

另一种是,我们可以维护一个队列的多段性。我们仍然始终每次取出的队首是最小元素、次小元素…不断更新下去,为了达成这一点我们需要开一个小根堆。那么什么时候就意味着一个状态维护完毕呢?答案是第一次出队。

前一种做法又叫SPFA,后一种又叫堆优化Dijkstra。

POJ3635

奥妙重重的优先队列搜索…

考虑维护一个状态$(i, V)$表示在第$i$剩下$V$升油没有加。那么该状态的分支有:

  • $(nxt, V - w_{i, nxt})$:前往第$nxt$个城市,并且花费$w_{i, nxt}$的油
  • $(i, V + 1)$:花费在$i$城市一升油的钱到下一个城市。

其实这就是一个优先队列转移图上的动态规划问题。用一个数组$dp[i][V]$保存状态的最小花费,$vis[i][V]$记录某个状态是否被访问过。注意该数组更新的时机应该是第一次出队,因为只有这个时候才意味着已经更新完成。也因此可以加一些小优化:如果某一状态已经被取出过,则花费更大的相同状态可以直接忽略,加上大概能快100ms。

当终点T的第一个状态被取出终止BFS并得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct node{
int v, id, oil;
node(){};
node(int a, int b, int c) {
v = a, id = b, oil = c;
}
bool operator < (const node& b) const {
return v > b.v;
}
};

struct michi{
int to, va;
michi(){};
michi(int a, int b) {
to = a, va = b;
}
};

vector<michi> road[1003];

inline void add_edge(int fr, int to, int va) {
road[fr].push_back(michi(to, va));
road[to].push_back(michi(fr, va));
}

int price[1003], dp[1003][103], n, m;
bool vis[1003][103];

int BFS(int c, int s, int e) {
priority_queue<node> q;
memset(dp, 0x3f, sizeof dp);
memset(vis, 0, sizeof vis);
q.push(node(0, s, 0));
dp[s][0] = 0;
while(!q.empty()) {
node tmp = q.top();
q.pop();
int w = tmp.id, o = tmp.oil, co = tmp.v;
//cout<<w<<" "<<o<<" "<<co<<endl;
if(vis[w][o]) continue;
vis[w][o] = 1;
if(w == e) return cout<<co<<endl, true;
if(o < c && !vis[w][o + 1] && dp[w][o] + price[w] < dp[w][o + 1]) {
q.push(node(co + price[w], w, o + 1));
dp[w][o + 1] = dp[w][o] + price[w];
}
for(int i = 0; i < road[w].size(); ++i) {
int ne = road[w][i].to, sp = road[w][i].va;
if(o >= sp && !vis[ne][o - sp] && dp[ne][o - sp] > co) {
dp[ne][o - sp] = co;
q.push(node(co, ne, o - sp));
}
}
}
return false;
}

int main() {
while(cin>>n>>m) {
for(int i = 1; i <= n; ++i) scanf("%d", &price[i]);
int ta, tb, tv;
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &ta, &tb, &tv);
add_edge(ta + 1, tb + 1, tv);
}
int q;
scanf("%d", &q);
int c, s, e;
while(q--) {
scanf("%d%d%d", &c, &s, &e);
if(!BFS(c, s + 1, e + 1)) puts("impossible");
}
}
return 0;
}
Author

LittleRewriter

Posted on

2018-02-27

Updated on

2021-07-28

Licensed under

Comments