SPFA 和负环

关于 SPFA，以及……#

~~……以及它死了~~，现在有意无意卡 $\texttt{SPFA}$ 似乎已经成为 OI 出题界的常规操作了……

$\texttt{Bellman-Ford}$ 算法的流程如下：

遍历 $n$ 个点
对于当前的点 $i$ ，遍历它的所有出边，并获取出边相连的点 $j$
进行松弛操作，将 $\operatorname{dist}_{j}$ 设为 $\operatorname{min}(\operatorname{dist}_j,\operatorname{dist}_i+w_{ij})$
若终点的最短路长度不为正无穷，则找到最短路；否则整张图不连通

但是在第三步中，每个点的最短距离不一定能够被更新——只有上一次松弛成功的点连接的边，才有可能引起下一次更新。做一个优化，减少不必要的出队。 $\texttt{SPFA}$ 引入了一个队列（类似于宽搜的队列），用来记录点的入队，避免不必要的松弛，具体如下：

1
void spfa(int s) {
2
    memset(dist, 0x3f, sizeof dist);
3

4
    queue<int> q;
5
    q.push(s);
6
    st[s] = true;
7
    dist[s] = 0;
8

9
    while (!q.empty()) {
10
        int t = q.front();
11
        q.pop();
12
        st[t] = false;
13

14
        for (int i = h[t]; ~i; i = edges[i].ne) {
15
            int j = edges[i].to;
16
            if (dist[j] > dist[t] + edges[i].w) {
17
                dist[j] = dist[t] + edges[i].w;
18
                if (!st[j]) {
19
                    q.push(j);
20
                    st[j] = true;
21
                }
22
            }
23
        }
24
    }
25
}

~~长得和 $\texttt{Dijkstra}$ 真的很像~~。

负环#

负环，顾名思义，就是边权之和为负数的环。在 $\texttt{SPFA}$ 中，有两种判负环的方式。

对每个点出队的次数进行计数，若某个点出队次数大于等于 $n$ （点数），则存在负环
求出到达当前点的最短路所经过的边数，若边数大于等于 $n$ 则存在负环

实际情况我们更喜欢用第二种，考虑极端情况—— $n$ 个点构成一个大负环，那么程序在这个环上跑一圈，每个点均只出队一次；要想使某个点出队 $n$ 次，就要经过 $n^2-1$ 条边，会造成严重的性能浪费。相较之下，第二种方案只需要在这个环上绕一圈即可判断负环，效率是极高的。

以 P3385 负环模板题为例，给出修改后的 $\texttt{SPFA}$ 核心代码：

1
bool spfa(int n) {
2
    memset(cnt, 0, sizeof cnt);
3
    memset(dist, 0x3f, sizeof dist);
4
    memset(st, false, sizeof st);
5

6
    queue<int> q;
7
    q.push(1);
8
    st[1] = true;
9
    dist[1] = 0;
10
    while (!q.empty()) {
11
        int t = q.front();
12
        q.pop();
13
        st[t] = false;
14
        for (int i = h[t]; ~i; i = edges[i].ne) {
15
            int j = edges[i].to;
16
            if (dist[j] > dist[t] + edges[i].w) {
17
                dist[j] = dist[t] + edges[i].w;
18
                cnt[j] = cnt[t] + 1;
19
                if (cnt[j] == n) return false;
20
                if (!st[j]) {
21
                    q.push(j);
22
                    st[j] = true;
23
                }
24
            }
25
        }
26
    }
27
    return true;
28
}

洛谷 P2850 [USACO06DEC] Wormhole G#

题目地址：P2850

题目难度：普及+/提高

题目来源：USACO 2006

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。
John 的每个农场有 $m$ 条小路（无向边）连接着 $n$ 块地（从 $1 \sim n$ 标号），并有 $w$ 个虫洞。
现在 John 希望能够从某块地出发，走过一条路径回到出发点，且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。
输入格式：
输入的第一行是一个整数 $T$ ，代表测试数据的组数。
每组测试数据的格式如下：
每组数据的第一行是三个用空格隔开的整数，分别代表农田的个数 $n$ ，小路的条数 $m$ ，以及虫洞的个数 $w$ 。
每组数据的第 $2$ 到第 $(m + 1)$ 行，每行有三个用空格隔开的整数 $u, v, p$ ，代表有一条连接 $u$ 与 $v$ 的小路，经过这条路需要花费 $p$ 的时间。
每组数据的第 $(m + 2)$ 到第 $(m + w + 1)$ 行，每行三个用空格隔开的整数 $u, v, p$ ，代表点 $u$ 存在一个虫洞，经过这个虫洞会到达点 $v$ ，并回到 $p$ 秒之前。
输出格式：
对于每组测试数据，输出一行一个字符串，如果能回到出发时刻之前，则输出 YES，否则输出 NO。
数据范围：
对于 ${100\%}$ 的数据， ${1 \le T \le 5}$ ， ${1 \le n \le 500}$ ， ${1 \le m \le 2500}$ ， ${1 \le w \le 200}$ ， ${1 \le p \le 10^4}$ 。

经典题。在题目中，我们不确定图的起点编号，图论中的经典技巧“虚拟源点”就派上用场了。虚拟源点是指新建一个原图中不存在的点，并把这个点向所有其他点连一条权值为 ${0}$ 的双向边，以实现多源汇最短路的求解。但实际操作中不一定需要真正的创建一个新点，可以从最短路初始的入队点入手——初始时先将 ${1\sim n}$ 号点全部入队。因为虚拟源点在初次松弛时，一定会遍历到所有相连点，即 ${1\sim n}$ 号点，然后松弛入队。因此开始将所有点加入队列和建立虚拟点并入队是等价的。

考虑把所有虫洞通道看作边权为 $-T$ 的有向边，这道题就转化成了判断是否存在负环的题目。也就是说我们直接敲一遍求负环的模板，就可以通过此题 $\downarrow$ 。

1
#include <bits/stdc++.h>
2
#define N 510
3
#define M 3010
4
using namespace std;
5

6
struct Edge {
7
    int to, ne, w;
8
} edges[M << 1];
9

10
int h[N], idx = 0;
11
int dist[N], cnt[N];
12
bool st[N];
13

14
void add(int u, int v, int w) {
15
    idx++;
16
    edges[idx].to = v;
17
    edges[idx].ne = h[u];
18
    edges[idx].w = w;
19
    h[u] = idx;
20
}
21

22
bool spfa(int n) {
23
    memset(dist, 0x3f, sizeof dist);
24
    memset(st, false, sizeof st);
25
    memset(cnt, 0, sizeof cnt);
26

27
    queue<int> q;
28
    for (int i = 1; i <= n; i++) {
29
        q.push(i);
30
        st[i] = true;
31
        dist[i] = 0;
32
    }
33
    while (!q.empty()) {
34
        int t = q.front();
35
        q.pop();
36

37
        st[t] = false;
38
        for (int i = h[t]; ~i; i = edges[i].ne) {
39
            int j = edges[i].to;
40
            if (dist[j] > dist[t] + edges[i].w) {
41
                dist[j] = dist[t] + edges[i].w;
42
                cnt[j] = cnt[t] + 1;
43
                if (cnt[j] == n) return true;
44
                if (!st[j]) {
45
                    q.push(j);
46
                    st[j] = true;
47
                }
48
            }
49
        }
50
    }
51
    return false;
52
}
53

54
int main() {
55
    ios::sync_with_stdio(false);
56
    cin.tie(nullptr);
57
    cout.tie(nullptr);
58

59
    int t;
60
    cin >> t;
61
    while (t--) {
62
        memset(h, -1, sizeof h);
63
        idx = 0;
64

65
        int n, m, k;
66
        cin >> n >> m >> k;
67
        int u, v, w;
68
        for (int i = 1; i <= m; i++) {
69
            cin >> u >> v >> w;
70
            add(u, v, w);
71
            add(v, u, w);
72
        }
73
        for (int i = 1; i <= k; i++) {
74
            cin >> u >> v >> w;
75
            add(u, v, -w);
76
        }
77
        cout << (spfa(n) ? "YES" : "NO") << endl;
78
    }
79
    return 0;
80
}

洛谷 P2868 [USACO07DEC] Sightseeing Cows G#

题目地址：P2868

题目难度：省选/NOI-

题目来源：USACO 2007

给你一张 $L$ 点 $P$ 边的有向图，第 $i$ 个点点权为 $F_i$ ，第 $i$ 条边边权为 $T_i$ 。
找一个环，设环上的点组成的集合为 $S$ ，环的边组成的集合为 $E$ ，最大化 $\dfrac{\sum_{u\in S}F_u}{\sum_{e\in E}T_e}$ 。
输入格式：
第一行是两个整数 $L$ 和 $P$
接下来 $L$ 行，每行一个整数代表 $F_i$
接下来 $P$ 行，每行三个整数 $a,b,t_i$ ，代表 $a$ 和 $b$ 之间有一条长为 $t_i$ 的边
输出格式：
一行一个数表示结果，保留两位小数
数据范围：
${1\leq L,F_i,T_i\leq1000},1\leq P\leq5000$

这道题需要用到分数规划相关知识，主要在对题目中算式的处理。根据题意可知，要求出一个环使得环中点权之和与边权之和比值最大。我们把环中的点权看作“性价比模型”里的“性能”，即 $a_i$ ；把边权看作“价格”，即 $b_i$ 。在分数规划中，当 $\sum a_i-d\cdot b_i\geq0$ 时，证明当前二分到的 $d$ 值小于正确答案；反之大于正确答案。根据这两条收缩二分区间，即可达到求解的效果。

在这道题里。考虑将上式变号，同乘 $-1$ ，变为 $\sum d\cdot b_i-a\leq0$ 。如果我们把边 $(u,v)$ 的边权重定义为 $d\cdot T_i-F_i$ ，就简化成“判断图上是否存在权值和为负的环”——负环的判断了。若形成负环，返回真，左区间收缩；反之收缩右区间。注意到负环的起始点并不确定，因此应用上面的超级源点思想来求解：

1
#include <bits/stdc++.h>
2
#define N 1010
3
#define M 5010
4
using namespace std;
5

6
struct Edge {
7
    int to, ne, w;
8
} edges[M << 1];
9
int h[N], idx = 0;
10
int p[N];
11
int cnt[N];
12
double dist[N];
13
bool st[N];
14
int L, P;
15
const double EPS = 1e-6;
16

17
void add(int u, int v, int w) {
18
    idx++;
19
    edges[idx].to = v;
20
    edges[idx].ne = h[u];
21
    edges[idx].w = w;
22
    h[u] = idx;
23
}
24

25
bool check(double mid) {
26
    memset(st, false, sizeof st);
27
    memset(cnt, 0, sizeof cnt);
28
    memset(dist, 127, sizeof dist);
29

30
    queue<int> q;
31
    for (int i = 1; i <= L; i++) q.push(i), st[i] = true, dist[i] = 0;
32

33
    while (!q.empty()) {
34
        int id = q.front();
35
        q.pop();
36

37
        st[id] = false;
38
        for (int i = h[id]; ~i; i = edges[i].ne) {
39
            int j = edges[i].to;
40
            double wfp = mid * edges[i].w - p[id];
41
            if (dist[j] > wfp + dist[id]) {
42
                dist[j] = wfp + dist[id];
43
                cnt[j] = cnt[id] + 1;
44
                if (cnt[j] == L) return true;
45
                if (!st[j]) {
46
                    q.push(j);
47
                    st[j] = true;
48
                }
49
            }
50
        }
51
    }
52
    return false;
53
}
54

55
int main() {
56
    ios::sync_with_stdio(false);
57
    cin.tie(nullptr);
58
    cout.tie(nullptr);
59

60
    memset(h, -1, sizeof h);
61

62
    cin >> L >> P;
63

64
    for (int i = 1; i <= L; i++) cin >> p[i];
65
    for (int j = 1; j <= P; j++) {
66
        int a, b, w;
67
        cin >> a >> b >> w;
68
        add(a, b, w);
69
    }
70
    double LEFT = 0, RIGHT = 1000;
71
    while (RIGHT - LEFT > EPS) {
72
        double mid = (LEFT + RIGHT) / 2;
73
        if (check(mid)) LEFT = mid;
74
        else RIGHT = mid;
75
    }
76
    cout << fixed << setprecision(2) << LEFT << endl;
77
    return 0;
78
}

SPOJ 2885 WORDRING - Word Rings#

题目地址：SPOJ 2885

题目难度：省选/NOI-

如果字符串A的结尾两个字符与字符串B的开头两个字符相匹配，我们称A与B能 “ 相连 ” ( 注意：A与B能相连，不代表B与A能相连 )
当若干个串首尾 “ 相连 ” 成一个环时，我们称之为一个环串（一个串首尾相连也算）
我们希望从给定的全小写字符串中找出一个环串，使这个环串的平均长度最长
1
intercommunicational
2
 alkylbenzenesulfonate
3
 tetraiodophenolphthalein
如上例：第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串又能与第一个串相连。按此顺序连接，便形成了一个环串。
长度为 20+21+24=65 ( 首尾重复部分需计算两次 ) ，总共使用了3个串，所以平均长度是 65/3≈21.6666
输入格式：
多组数据每组数据第一行一个整数n，表示字符串数量接下来n行每行一个长度小于等于1000的字符串读入以n=0结束
输出格式：
若不存在环串，输出”No solution.”。否则输出最长的环串平均长度。
Translated by @远藤沙椰
数据范围：
${1\leq n\leq10^5}$

这道题让我们最大化一个比值，再次把目光放到分数规划上来。如同上一道题，这道题也可以转化为分数规划+判负环的算法求解。难点在于如何把一个一个的字符串建成图。

首先考虑把每个字符串当成一个点，如果两个字符串能首尾相接（直接判断首位两个字符），就连边，边权为两字符串长度之和。这样建图有没有什么不妥之处？

观察到数据范围， $n$ 的极端情况是十万，假设我们有十万个完全相同的字符串，那么点数将是 ${10^5}$ ，两两连边，边数是 ${10^{10}}$ 。完全失败！

换一种思路，把首位两个字符当作点，把一个字符串拆成两点和一边（~~化学键~~），边权是该字符串的长度。此时的最大点数将是 ${26^2=676}$ ，最大边数是 ${10^5}$ （字符串总数）。然后就可以用分数规划求解了。

从基本模型出发，得到 $\sum a_i-d\cdot k\geq0$ 。不难发现此时 $a_i$ 代表字符串的长度， $k$ 代表所用字符串的数量（经过的边数）。求和是从 ${1\sim k}$ 的，每项展开得 $(a_1-d)+(a_2-d)+\dots+(a_k-d)$ ，新边权就是 $w_{ij}-d$ 。像上一道题那样不等号两边同乘以 $-1$ ，得到 $\sum d\cdot k-a_i\leq0$ ，就可以转化为一个判负环问题。 $\texttt{SPFA}$ 判负环使用 $\texttt{BFS}$ 会稍慢（会TLE），这里改用 $\texttt{DFS}$ 来实现。

1
#include <bits/stdc++.h>
2

3
#define N 700
4
#define M 100010
5
#define distinct(a, b) ((a - 'a') * 26 + b - 'a')
6
#define recover(x) (string(1, char(x / 26 + 'a')) += char(x % 26 + 'a'))
7

8
using namespace std;
9

10
struct Edge {
11
    int to, ne, w;
12
} edges[M << 1];
13
int h[N], idx = 0;
14
const double EPS = 1e-6;
15
int n;
16
double dist[N];
17
bool st[N];
18

19
void add(int u, int v, int w) {
20
    idx++;
21
    edges[idx].to = v;
22
    edges[idx].ne = h[u];
23
    edges[idx].w = w;
24
    h[u] = idx;
25
}
26

27
bool spfa_dfs(int u, double d) {
28
    if (st[u]) return true;
29
    st[u] = true;
30
    for (int i = h[u]; ~i; i = edges[i].ne) {
31
        int j = edges[i].to;
32
        double wfp = d - edges[i].w;
33
        if (dist[j] > dist[u] + wfp) {
34
            dist[j] = dist[u] + wfp;
35
            if (spfa_dfs(j, d)) return true;
36
        }
37
    }
38
    st[u] = false;
39
    return false;
40
}
41

42
bool check(double d) {
43
    memset(dist, 0, sizeof dist);
44
    memset(st, false, sizeof st);
45

46
    for (int i = 0; i < 676; i++) {
47
        if (spfa_dfs(i, d)) return true;
48
    }
49
    return false;
50
}
51

52
int main() {
53
    ios::sync_with_stdio(false);
54
    cin.tie(nullptr);
55
    cout.tie(nullptr);
56

57
    while (cin >> n && n) {
58
        memset(h, -1, sizeof h);
59
        idx = 0;
60

61
        for (int i = 1; i <= n; i++) {
62
            string s;
63
            cin >> s;
64
            if (s.length() < 2) continue;
65
            add(distinct(s[0], s[1]), distinct(s[s.length() - 2], s[s.length() - 1]), s.length());
66
        }
67
        double L = 0, R = 1e5;
68
        while (R - L > EPS) {
69
            double mid = (L + R) / 2;
70
            if (check(mid)) L = mid;
71
            else R = mid;
72
        }
73
        if (L > EPS) cout << L << endl;
74
        else cout << "No solution." << endl;
75
    }
76
    return 0;
77
}

相似题目：UVA 11090、P3199、P3288

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

关于 SPFA，以及……#

负环#

洛谷 P2850 [USACO06DEC] Wormhole G#

洛谷 P2868 [USACO07DEC] Sightseeing Cows G#

SPOJ 2885 WORDRING - Word Rings#

支持与分享

评论区

音乐

目录