「SPFA」如何优雅的卡掉SPFA

20182018771919 日,某位同学在 NOI Day1 T1\text{NOI Day1 T1} 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢?

10060,AgCu100 \rightarrow 60, Ag \rightarrow Cu

最终,他因此没能与理想的大学达成契约

相信大家只要学过 OI\text{OI} 的人都知道 SPFA\text{SPFA} 求最短路吧(

SPFA\text{SPFA} 代码简洁,简单易懂,是初学者学习最短路最好的算法 QAQ

毫无优化的 SPFA\text{SPFA} 代码:

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
inline int spfa(const int &s,const int &t,const int &n){
for (int i = 1; i <= n; i++){
node[i].dist = inf;
node[i].inQueue = false;
}
queue<Node *> q;
q.push(&node[s]);
node[s].dist = 0;
node[s].inQueue = true;
while(!q.empty()){
Node *u = q.front();
q.pop();
u->inQueue = false;
for(Edge *e = u->firstEdge; e; e = e->next){
Node *v = e->t;
if(v->dist > u->dist + e->w){
v->dist = u->dist + e->w;
if(!v->inQueue){
q.push(v);
v->inQueue = true;
}
}
}
}
return node[t].dist;
}

// spfa(start, end, n)

多么简洁..多么好看....多么..算了窝编不下去惹 QAQ

其实 SPFA\text{SPFA} 是来用一个假复杂度顶替 Bellman-Ford\text{Bellman-Ford} 的名字

Hack SPFA

我们先来看看常见的卡 SPFA\text{SPFA} 的方法

构造网格图

这个是最基础的卡掉 SPFA\text{SPFA} 的方法(

但是最基础的网格图也能卡掉 80%80\%SPFA\text{SPFA}

网格图是如何卡 SPFA\text{SPFA} 的呢, 因为在网格图中走错一次路可能导致很高的额外开销 QAQ

Code

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
#include <bits/stdc++.h>

using namespace std;

struct edge { int u, v, w; };

vector<edge> v;

int id[5000][5000], n = 9, tp, m = 42866 / n, a[1000000];

int r() {
return(rand() );
/* return rand()<<13|rand(); */
}


int main () {
freopen( "in.txt", "w", stdout );
srand( time( 0 ) );
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= m; ++j )
id[i][j] = ++tp, a[tp] = tp;
/* random_shuffle(a+1,a+tp+1); */
int SIZE = 29989;
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= m; ++j )
{
if ( i < n )
{
v.push_back( edge { id[i][j], id[i + 1][j], 1 } );
v.push_back( edge { id[i + 1][j], id[i][j], 1 } );
if ( j < m )
{
if ( 1 )
v.push_back( edge { id[i][j], id[i + 1][j + 1], r() % SIZE + 10 } );
else v.push_back( edge { id[i + 1][j + 1], id[i][j], r() % SIZE + 10 } );
}
}
if ( j < m )
{
v.push_back( edge { id[i][j], id[i][j + 1], r() % SIZE + 10 } );
v.push_back( edge { id[i][j + 1], id[i][j], r() % SIZE + 10 } );
}
}
fprintf( stderr, "[%d,%d,%d]", v.size(), n, m );
random_shuffle( v.begin(), v.end() );
/* printf("%d %d %d\n",tp,v.size(),2); */
printf( "%d %d\n", tp, v.size() );
for ( int i = 0; i < v.size(); ++i )
printf( "%d %d %d\n", a[v[i].u], a[v[i].v], v[i].w );
/*
* for(int i=1;i<=10;++i)printf("%d ",a[id[1][10*i]]);
* printf("%d %d",a[1],a[2]);
*/
}

链套菊花

这样会使得队列更新菊花的次数非常高 QAQ


介绍完了几种常见的卡 SPFA\text{SPFA} 的方法,我们再来看一下 SPFA\text{SPFA} 的几种优化 极其分别如何Hack

LLL 优化

方法 & 原理

设队首元素为 ii ,每次弹出时进行判断,队列中所有 distdist 值的平均值为 xx ,若 dist(i)>xdist(i)>x 则将 ii 插入到队尾,查找下一元素,直到找到某一i使得 dist(i)xdist(i)\le x,则将i出对进行松弛操作

Hack

对于单纯的平均值我们可以直接构造极端值来卡 QAQ

11 连接一条权值巨大的边,这样 LLL\text{LLL} 就失效了

SLF 优化

方法 & 原理

设要加入的节点是 jj ,队首元素为 ii,若 dist(j)<dist(i)dist(j) < dist(i),则将j插入队首,否则插入队尾

Hack

对于这种优化我们可以采取我们网格图的策略

用链套菊花,在链上用几个并列在一起的小边权边就能欺骗算法多次进入菊花,从而时间复杂度巨大 QAQ

Code

这里给一下代码,主要这个是可以同时再用 LLL\text{LLL} 优化的

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
char str[maxn][maxn];
int vis[maxn][maxn],dis[maxn][maxn],n,m;

int ans[30],sum,cnt;

int dx[] = {-1,-1,0,1,1,1,0,-1},dy[] = {0,1,1,1,0,-1,-1,-1};

deque<PII>q;
void spfa() {
while(!q.empty()) {
PII f = q.front();q.pop_front();
//LLL优化
if(dis[f.fi][f.se] * cnt > sum) {
q.push_back(f);
continue;
}

sum -= dis[f.fi][f.se]; cnt--;
vis[f.fi][f.se] = 0;

for( int i = 0; i < 8; i++ ){
int nx = f.fi + dx[i],ny = f.se + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > m)continue;
int w = (str[nx][ny] != str[f.fi][f.se]);
if(dis[nx][ny] > dis[f.fi][f.se] + w){
dis[nx][ny] = dis[f.fi][f.se] + w;
if(!vis[nx][ny]){
vis[nx][ny] = 1;
//SLF优化
if(dis[nx][ny] < dis[q.front().fi][q.front().se]){
q.push_front(mp(nx,ny));
} else {
q.push_back(mp(nx,ny));
}
sum += dis[nx][ny];cnt++;
}
}
}
}
}

void init() {
cl(dis,INF);
cl(vis,0);
cl(ans,INF);
sum = cnt = 0;
}

容错机制

如果我们遇到了小边权,我们可以采用容错机制来防止被 Hack

每次将入队结点距离和队首比较的时候,如果比队首大超过一定值 ww 则插入至队尾,否则插入队头.

这样看起来就无懈可击了(

对于这个一定值ww,我们最好取

w=for each edge(u, v, dist)distw = \sqrt {\sum_{\text{for each edge(u, v, dist)}} \text{dist}}

Hack 容错机制

小边权当然是无解的…..

我们分析时间复杂度,显然的是 O((n+m)×w)O((n+m) \times \sqrt w)

我们直接开大边权即可,比如把 for each edge(u, v, dist)dist\sqrt {\sum_{\text{for each edge(u, v, dist)}} \text{dist}} 开到 10610^6

SLF + Swap

每当队列改变时,如果队首距离大于队尾,则交换首尾

这个 SLF 看起来很弱,但却通过了所有 Hack 数据。而且, 非常难卡

Hack SLF + Swap

然而这个与卡 SLF 类似,外挂诱导节点即可(

mcfx 优化

方法 & 原理

mcfx神犇

在第 [l,r][l,r] 次访问一个结点时,将其放入队首,否则放入队尾。通常取 l=2,r=Vl=2, r=\sqrt V

Hack

这个优化在网格图上跑的飞快….

但是遇到菊花图就凉了

NTR 优化

牛头人优化

方法 & 原理

维护一个叫临时最短路树的东西,刚开始只有一个源节点

SPFA\text{SPFA} 的过程中,每次松弛 (u,v)(u, v) 边时将 vv 的父亲设为 uuvv 是有可能有后代的,所以将其所有后代的对应 inQueue\text{inQueue}标记清除;在 SPFA\text{SPFA} 过程中如果发现队头节点的 inQueue\text{inQueue} 为空那么跳过。理由是如果我们能松弛 (u,v)(u, v) 边,那么从 (u,v)(u, v) 走势必比以前走过的那种走法好。将这个步骤称为 NTR\text{NTR}

随着深度趋近无穷大(真的很大),NTR\text{NTR} 的频率(频率指 22NTR\text{NTR} 之间需要的 iteration\text{iteration} 数的倒数 也就是说我们把 BFS\text{BFS} 看成是一个前进的过程 一次 iteration\text{iteration} 就是一次前进)趋近于 1logn1\over \log n

这是一个很糟的结论,不过我们有办法避开它。在迭代过程中强行把一些不能松弛的边 NTR\text{NTR} 一下(目的是破坏子树)就行了,使得频率是 0.50.5

那么我们知道,NTR\text{NTR}extra\text{extra} 时间复杂度为 NTR\text{NTR} 频率 x 顶点数 x NTR\text{NTR} 代价 其中 NTR\text{NTR} 代价是 mnm\over n(理解这个的话 想象你要 NTR\text{NTR} 出一棵子树,你要积累 22 层...) 然后也就是 0.5×n×mn=0.5×m{0.5\times n\times m\over n}=0.5\times m

上面除了NTR\text{NTR} 操作外我们还看见了 dfsdfs 找儿子操作和 dfsdfs 重置 label\text{label} 操作,看起来慌得一笔都是 O(m)O(m) 的 其实这几个的时间和 NTR\text{NTR} 一模一样;

时间复杂度 O(nlognlogmn)O(m+n)O(n\log n \log{m\over n})\to O(m+n)

Code

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
inline int SPFA() {
int i, j, x, cnt = 0;
queue<int> Q;
memset(d, 0x3f, sizeof(d));
d[S] = 0;
Q.push(S);
setv(S, 1);
while(!Q.empty()) {
x = Q.front();
Q.pop();
cnt ++;
if(!query(x)) continue;
for(i = 0;i < G[x].size();i ++) {
Edge &e = edge[G[x][i]];
if(d[x] + e.w < d[e.v]) {
d[e.v] = d[x] + e.w;
Q.push(e.v);
setc(e.v, 0);
setv(e.v, 1);
if(lca(e.v, x) == e.v) {
return 0;
}
int f = getfa(e.v);
linkcut(f, e.v, x);
}
}
}
return 1;
}

总结

人生苦短,慎用SPFA\text{SPFA}

本文转自知乎Hack 之王(

坚持原创技术分享,您的支持将鼓励我继续创作!