SPFA求负环

时间复杂度

  • O(km)，最坏O(nm)

两种方法：

  • 法一：统计每个点入队的次数，如果某个点入队n次，则说明存在负环
  • 法二：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数>=n，则说明存在负环
  • 都是基于抽屉原理（鸽巢原理）
  • 一般用法二，时间复杂度更低

常见问题：

  • 为什么等价于将所有点入队？
    解释：建立虚拟源点，并将虚拟源点和其他所有点连一条边
  • 为什么求负环时不需要将其他点初始化为正无穷？
    如果存在负环，则dist最终为-INF，所以dist无论时INF还是0无所谓，会绕负环无穷次，对于无穷而言具体的值就无所谓了。

关于TLE的优化

  • 做题前要思考如何建图方便，因为spfa时间复杂度很危险，如何降低点和边的数量使关键
  • 若时间复杂度接近O(nm)则可以默认其已经含有负环，具体可根据经验，(比如，当所有的入队次数超过2n时，我们就认为图中有很大可能时存在负环的)，缺点是不太稳定
  • 将队列转化为栈，面对找负环的问题一般效率比较好，比上面的trick较稳定一些

代码如下：

队列 + trick(小花招): 200ms +

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
int n, m1, m2;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

// true有负环，false无负环
bool spfa()
{
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = true;
    }
    
    while(hh != tt)
    {
        int t = q[hh ++ ];
        if(hh == N) hh = 0;
        
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    st[j] = true;
                    q[tt ++ ] = j;
                    if(tt == N) tt = 0;
                }
            }
        }
    }
    
    return false;
}

队列改栈: 400ms+

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 700, M = 100010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
double dist[N];
int q[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool check(double mid)
{
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    
    int tt = 0;
    for (int i = 0; i < 676; i ++ )
    {
        q[ ++ tt] = i;
        st[i] = true;
    }
    
    int count = 0;
    while(tt)
    {
        int t = q[tt -- ];
        
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i] - mid)
            {
                dist[j] = dist[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= N) return true;
                if(!st[j])
                {
                    st[j] = true;
                    q[ ++ tt] = j;
                }
            }
        }
    }
    
    return false;
}

int main()
{
    while(scanf("%d", &n), n)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        
        char str[1010];
        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            int len = strlen(str);
            if(len >= 2) 
            {
                int left = (str[0] - 'a') * 26 + str[1] - 'a';
                int right = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                add(left, right, len);
            }
        }
        
        if(!check(0)) puts("No solution");
        else 
        {
            double l = 0, r = 1010;
            while(r - l > 1e-4)
            {
                double mid = (l + r) / 2;
                if(check(mid)) l = mid;
                else r = mid;
            }
            printf("%lf\n", r);
        }
    }
    
    return 0;
}