grant's Blog

记录生活中的点点滴滴

算法基础课笔记（二十）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 4.3k 阅读时长 ≈ 4 分钟

例题2：852. spfa判断负环（模板题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。

输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
Yes

判断负环需要在朴素spfa基础上维护一个cnt数组，存放当前最短路的边数。

只要过程中某次cnt值>=n，说明经过某个点两次，存在负环。

参考题解： https://www.acwing.com/solution/content/6336/。（虚拟源点的解释很到位）

题目要求图中是否存在负环，而不是问是否存在从1号点开始的负环，所以每个点都需要入队。

在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。那么原图有负环等价于新图有负环。此时在新图上做spfa可以找到负环，等价于新图有负环，等价于原图有负环。

求负环时由于只需要判断负环是否存在，不需要求出路径的具体长度，因此dist数组就不需要初始化了。而且dist数组初始化不影响找负环。因为只要有负环存在，就必然有某些点的距离是负无穷，所以不管距离被初始化成何值，都一定严格大于负无穷，所以一定会被无限更新。

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
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)
const int N = 2010,M = 1e4+5;
int d[N];
int h[N],e[M],w[M],ne[M],idx;// 邻接表存储，不需要判重边
int n,m;
bool s[N];// 记录节点是否进入队列
int cnt[N];

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

int spfa(){
    queue<int> q;// 队列优化
    for (int i = 1;i <= n;i ++){
        q.push(i);
        //s[i] = true;
    }
    
    while (q.size()){
        int t = q.front();
        q.pop();
        //s[t] = false;
        
        //从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
        for (int i = h[t]; ~i;i = ne[i]){// 拓展队头t的所有后继节点
            int j = e[i];
            if (d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i];// 边松弛
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                q.push(j);// j的距离发生更新，加入队列
            }
        }
    }
    return false;
}

int main(){
    IOS;
    
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0;i < m;i ++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();// 题目限制边权绝对值不超过10000
    if (t) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

所有st[]判断都去掉能快3倍左右，因为判负环的原理是看cnt数组是否大于n,cnt更新的前提是当前点更新,而队列的存在让我不能够很快的访问同一个点。当去掉判断以后,很快我就能重复遇到相邻的点,这样能够快速增加cnt的值,所以会快很多。

3.6.5：Floyd 算法

是用来求任意两个结点之间的最短路的，利用DP思想。

复杂度比较高，但是常数小，容易实现，也可以处理负权边。效率比执行 n次 Dijkstra 算法要好。

参考题解1： https://www.acwing.com/solution/content/6337/。

参考题解2： https://www.acwing.com/solution/content/20441/。（思路到位）

用邻接矩阵来存图。

f[k,i,j]代表（k的取值范围是从1到n），在考虑了从1到k的节点作为中间经过的节点时，从i到j的所有路径的最小值。

形式化说明如下：

​ f[k][i][j]可以从两种情况转移而来：
​ 【1】从f[k−1][i][j]转移而来，表示i到j的最短路径不经过k这个节点
​ 【2】从f[k−1][i][k]+f[k−1][k][j]转移而来，表示i到j的最短路径经过k这个节点

那么f[k,i,j] = min(f[k-1,i,j], f[k-1,k,i] + f[k-1,k,j])。

因此在计算第k层的f[i,j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。

可以把k这一维度去掉，降低空间复杂度，f[i,j] = min(f[i,j], f[i,k] + f[k,j])。

例题：854. Floyd求最短路（模板题）

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
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。

输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围
1≤n≤200,
1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)
const int N = 210,INF = 0x3f3f3f3f;
int d[N][N];// 邻接矩阵
int n,m,k;

void floyd(){
    for (int k = 1;k <= n;k ++)// k必须放第一重循环
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
}

int main(){
    IOS;
    
    cin >> n >> m >> k;
    
    memset(d, 0x3f, sizeof d);// 邻接矩阵初始化为INF
    for (int i = 1; i <= n; i ++ ) d[i][i] = 0;// 消除自环
    
    while (m -- ){
        int x,y,z;
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y],z);// 重边取权值最小的
    }
    floyd();
    while (k -- ){
        int x,y;
        cin >> x >> y;
        int t = d[x][y];
        if (t > INF/2) cout << "impossible\n";
        else cout << t << '\n';
    }
    return 0;
}

询问可能会问到自身到自身的距离的，所以d[i][i]要初始化为0。否则可能会得到自身到自身的距离为INF级别的类似错误答案。

Floyd和BF算法类似，会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新，因此就算不存在x到y的最短路，距离INF会发生改变，但不至于超过一半，所以用INF/2来判断。

五种最短路的简单文字总结：

Dijkstra-朴素 O(n^2)
初始化距离数组, dist[1] = 0, dist[i] = inf;
for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
将不在S中dist_min的点->t
t->S加入最短路集合
用t更新到其他点的距离

Dijkstra-堆优化 O(mlogn)
利用邻接表，优先队列
在priority_queue<PII,vector<PII>,greater<PII>> heap;中将返回堆顶
利用堆顶来更新其他点，并加入堆中类似宽搜

Bellman_ford O(nm)
注意串联反应需要备份, struct Edge{int a,b,c} Edge[M];
初始化dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
松弛k次，每次访问m条边

Spfa O(n)∼O(nm)
利用队列优化仅加入修改过的地方
for k次
for 所有边利用宽搜模型去优化bellman_ford算法
更新队列中当前点的所有出边

Floyd O(n^3)
初始化d
k, i, j 去更新d

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