算法图算法

负环

字数统计: 2k字   |   阅读时长: 10分
,

摘要: 负环

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

负环

在图论中，如果一条边的权值是负数，则为负权，如果图中存在一个环，还上各个边的权值之和为负数，则为负环。

在 带权图最短路径 中，各种单源最短路径算法有一些适用条件：

  • dijkstra: $O(n^{2})$，不能处理负权
  • heap-dijkstra: $O(m\log n)$，不能处理负权
  • bellman-ford: $O(nm)$，可以处理负权，无负环时，最短路包含的边数 $< n$，n - 1 轮迭代之和一定收敛
  • dpfa: $O(km)~O(nm), k是较小的常数$，可以处理负权，负环只是会增加出入队次数

如果图中存在负环，那么无论多少轮迭代，总存在有向边 $(x,y,z)$，使得 $d[y] > d[x] + z$，bellman-ford 和 spfa 永远不会收敛。

负环的判定法则与算法

Bellman-Ford

如果经过 n 轮迭代，仍未收敛，即仍能产生可以更新的边，则图中存在负环。

n - 1 轮之内收敛，即所有边满足三角形不等式，则图中无负环。

代码模板 (C++)

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
struct To
{
    int v;
    double w;
    To(int v, double w):v(v),w(w){}
};

bool bellman_ford(vector<vector<To> >& g, int start, vector<bool>& visited)
{
    // bellman ford  O(VE)
    // 可以检测负环

    int N = g.size() - 1;
    vector<double> d(N + 1, INT_MAX / 2);
    d[start] = 0.0;

    // 进行 N - 1 轮松弛
    // 因为任意两点之间最短路最多包含 N - 1 条边
    for(int cnt = 1; cnt <= N; ++cnt)
    {
        // u: 源节点，v: 子节点, w: uv 的权
        bool update = false;
        for(int u = 1; u <= N; ++u)
        {
            if(abs(d[u] - INT_MAX / 2) < eps) continue;
            for(To &son: g[u])
            {
                int v = son.v;
                double w = son.w;
                // 判断能否通过 u -> v 缩短 d[v] (松弛)
                if(d[u] + w + eps < d[v])
                {
                    update = true;
                    if(cnt >= N)
                        return true; // 负环
                    d[v] = d[u] + w;
                }
            }
        }
        if(!update)
            break;
    }
    for(int i = 1; i <= N; ++i)
    {
        if(abs(d[i] - INT_MAX / 2) > eps)
            visited[i] = true;
    }
    return false;
}

bool negative_cycle(vector<vector<To> >& g)
{
    int N = g.size() - 1;
    vector<bool> visited(N + 1, false);
    for(int i = 1; i <= N; ++i)
    {
        if(visited[i]) continue;
        if(bellman_ford(g, i, visited))
            return true;
    }
    return false;
}

spfa

设 cnt[x] 表示从 1 到 x 的最短路径包含的边数，cnt[1] = 0，当更新 d[y] = d[x] + z 时，同时更新 cnt[y] = cnt[x] + 1，此时若 cnt[y] >= n，则图中有负环。算法正常结束则没有负环。

代码模板 (C++)

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
struct To
{
    int v;
    double w;
    To(int v, double w):v(v),w(w){}
};

bool spfa(vector<vector<To> >& g, int start, vector<bool>& visited)
{
    // 与 bellman ford 相同, O(VE)
    // 可以检测负环

    int N = g.size() - 1;
    vector<double> d(N + 1, INT_MAX / 2);
    d[start] = 0;
    queue<int> q;
    q.push(start);

    // 记录每个点到 start 的节点个数
    vector<int> cnt(N + 1, 0);
    cnt[start] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(To &son: g[u])
        {
            int v = son.v;
            double w = son.w;
            if(abs(d[v] - INT_MAX / 2) < eps || d[v] > d[u] + w + eps)
            {
                cnt[v] = cnt[u] + 1;
                if(cnt[u] > N)
                    return true; // 若 son 到 start 的节点个数大于 N 了说明有负环
                // 当最短距离发生变化且不在队列中时，将该节点加入队列
                d[v] = d[u] + w;
                q.push(v);
            }
        }
    }
    for(int i = 1; i <= N; ++i)
    {
        if(abs(d[i] - INT_MAX / 2) > eps)
            visited[i] = true;
    }
    return false;
}

bool negative_cycle(vector<vector<To> >& g)
{
    int N = g.size() - 1;
    vector<bool> visited(N + 1, false);
    for(int i = 1; i <= N; ++i)
    {
        if(visited[i]) continue;
        if(spfa(g, i, visited))
            return true;
    }
    return false;
}

题目

一张有向图，每个点 i 有一个权值 wv[i]，每条边 j 也有一个权值 we[j]，求图中的一个环，使得环上各个点的权值之和除以环上各个边的权值之和最大。求这个最大值。

算法：01分数规划、负环

这是 01分数规划 问题。

记环上有 t 个点，t 条边，各个点为 $v = \{v_{1}, v_{2}, …, v_{t}\}$，各个边为 $e = \{e_{1}, e_{2}, …, e_{t}\}$，要求以下分数规划的最大值：

二分出 mid 之后，看是否存在环使得 $\frac{\sum_{i=1}^{t}wv[i]}{\sum_{i=1}^{t}we[i]} > mid$，即判断 $\sum_{i=1}^{t}(mid * we[i] - wv[i]) < 0$：

  • 若成立：则 mid 比所求的最大值小，比 mid 小的不是答案，left = mid
  • 若不成立：则 mid 比所求的最大值大，比 mid 大的不是答案，right = mid

判断过程：建图，没有点权，对于边 $e = uv$，边权为 mid * we[e] - wv[u]，判定 $\sum_{i=1}^{t}(mid * we[i] - wv[i]) < 0$ 是否成立的意思就是判定图中是否存在负环。

代码 (C++)

spfa 勉强过，bellman-ford 超时

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <iomanip>
#include <queue>

using namespace std;

const double eps = 1e-8;

struct Edge
{
    int u,v;
    int w;
    Edge(int u, int v, int w):u(u),v(v),w(w){}
};

struct To
{
    int v;
    double w;
    To(int v, double w):v(v),w(w){}
};

bool spfa(vector<vector<To> >& g, int start, vector<bool>& visited)
{
    // 与 bellman ford 相同, O(VE)
    // 可以检测负环

    int N = g.size() - 1;
    vector<double> d(N + 1, INT_MAX / 2);
    d[start] = 0;
    queue<int> q;
    q.push(start);

    // 记录每个点到 start 的节点个数
    vector<int> cnt(N + 1, 0);
    cnt[start] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(To &son: g[u])
        {
            int v = son.v;
            double w = son.w;
            if(abs(d[v] - INT_MAX / 2) < eps || d[v] > d[u] + w + eps)
            {
                cnt[v] = cnt[u] + 1;
                if(cnt[u] > N)
                    return true; // 若 son 到 start 的节点个数大于 N 了说明有负环
                // 当最短距离发生变化且不在队列中时，将该节点加入队列
                d[v] = d[u] + w;
                q.push(v);
            }
        }
    }
    for(int i = 1; i <= N; ++i)
    {
        if(abs(d[i] - INT_MAX / 2) > eps)
            visited[i] = true;
    }
    return false;
}

bool bellman_ford(vector<vector<To> >& g, int start, vector<bool>& visited)
{
    // bellman ford  O(VE)
    // 可以检测负环

    int N = g.size() - 1;
    vector<double> d(N + 1, INT_MAX / 2);
    d[start] = 0.0;

    // 进行 N - 1 轮松弛
    // 因为任意两点之间最短路最多包含 N - 1 条边
    for(int cnt = 1; cnt <= N; ++cnt)
    {
        // u: 源节点，v: 子节点, w: uv 的权
        bool update = false;
        for(int u = 1; u <= N; ++u)
        {
            if(abs(d[u] - INT_MAX / 2) < eps) continue;
            for(To &son: g[u])
            {
                int v = son.v;
                double w = son.w;
                // 判断能否通过 u -> v 缩短 d[v] (松弛)
                if(d[u] + w + eps < d[v])
                {
                    update = true;
                    if(cnt >= N)
                        return true; // 负环
                    d[v] = d[u] + w;
                }
            }
        }
        if(!update)
            break;
    }
    for(int i = 1; i <= N; ++i)
    {
        if(abs(d[i] - INT_MAX / 2) > eps)
            visited[i] = true;
    }
    return false;
}

bool check(const vector<int>& wv, const vector<Edge>& edges, double mid)
{
    int N = wv.size() - 1;
    vector<vector<To>> g(N + 1);
    for(const Edge &e: edges)
        g[e.u].push_back(To(e.v,  (double)mid * (double)e.w - wv[e.u]));
    vector<bool> visited(N + 1, false);
    for(int i = 1; i <= N; ++i)
    {
        if(visited[i]) continue;
        if(bellman_ford(g, i, visited))
        // if(spfa(g, i, visited))
            return true;
    }
    return false;
}

int main()
{
    // fstream fin("negacycle.test");
    int L, P;
    cin >> L >> P;
    vector<int> wv(L + 1);
    for(int i = 1; i <= L; ++i)
        cin >> wv[i];
    vector<Edge> edges;
    for(int i = 1; i <= P; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges.emplace_back(u, v, w);
    }
    double left = 0.0, right = 1e9;
    while(abs(right - left) > eps)
    {
        double mid = (left + right) / 2;
        if(check(wv, edges, mid))
            left = mid;
        else
            right = mid;
    }
    cout << setiosflags(ios::fixed) << setprecision(2);
    cout << left << endl;
}
Share