头像

cht

ACWING的忠实粉丝:cht蒟蒻。


访客:20449

离线:6小时前



cht
7小时前

bellmam-ford算法与SPFA

这期我们来讲一讲如何处理负边权的最短路断路问题。

一、bellmam-ford算法。

大家放心。
看着这个高大上的名字。
我可以告诉大家,这个算法最难的地方就是这个算法的名字很难拼……
(而且这个算法很傻)
算法过程如下:
先进行n-1次代谢
接着枚举每条边
然后用以前的边更新这个边………………
没了。
唯一的难点就是需要用一个last数组存上次使用的点。
简单说就是备份数组
但是这里大家要学会一个东西:

memcpy

那么ta是干蛤的呢?
cpy——复制。
备份的时候需要把数组复制一下。

memcpy(last, dist, sizeof dist);

最后我们来看一下bellmam-ford算法的板子。

void bellmamford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0 ; i < k; i ++)
    {
        memcpy(last, dist, sizeof dist);
        for(int j = 0; j < m; j ++)
        {
            auto e = es[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.w);
        }
    }
}

关键这个算法最弱的地方就是——

它存边是用的结构体………………………………………………

但是这个算法有一个特性,就是因为第二次遍历k条边(如上板子),
所以这个算法可以求出有边数限制的最短路。
而其他算法就做不到。
所以,

暴力出奇迹!

我们看一下这道题
题目描述:
给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数

请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。

注意:图中可能 存在负权回路

输入格式
第一行包含三个整数n,m,k。

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

输出格式
输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径,则输出“impossible”。

数据范围

1 ≤ n, k ≤ 500,
1 ≤ m ≤ 10000,

任意边长的绝对值不超过10000。

输入样例:

3 3 1
1 2 1
2 3 1
1 3 3

输出样例:

3

有人可能要问我,啥是负权回路?
就是一个回路的权值和是负数。
如果这个点在1-n的任一条路径上,

最短路就没了

因为每次在那里转一圈最短路-1,可以转无数圈。
但当这个玩意遇到bellmam-ford算法。
火花没撞出来,脑花到“装”出来了,太慢了……
遇到spfa才有用(见后)
好了继续回到正题。
这题的求法应该很弱吧。
直接bellmam-ford一波。
首先写一个struct,存所以的边。

struct e
{
    int a, b, w;
}es[M];

读入所有数,放进es。

cin >> n >> m >> k;
for(int i = 0; i < m; i ++)
{
    int a, b, w;
    cin >> a >> b >> w;
    es[i] = {a, b, w};
} 

bellmam-ford一遍dist数组,别忘记开last数组存储。
重复一遍板子。

void bellmamford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0 ; i < k; i ++)
    {
        memcpy(last, dist, sizeof dist);
        for(int j = 0; j < m; j ++)
        {
            auto e = es[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.w);
        }
    }
}

最后判断一下,如果dist[n]大于一个很大的数,没有最短路,否则有。

if(dist[n] > 0x3f3f3f3f / 2)  cout << "impossible";
else cout << dist[n];

为啥这里是0x3f3f3f3f / 2呢?
因为图中存在负权边。
完整代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<limits.h>
using namespace std;
const int N = 510, M = 10010;
struct e
{
    int a, b, w;
}es[M];
int n, m, k, dist[N], last[N];
void bellmamford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0 ; i < k; i ++)
    {
        memcpy(last, dist, sizeof dist);
        for(int j = 0; j < m; j ++)
        {
            auto e = es[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.w);
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        es[i] = {a, b, w};
    } 
    bellmamford();
    if(dist[n] > 0x3f3f3f3f / 2)  cout << "impossible";
    else cout << dist[n];
    return 0;
}

二、SPFA

emmspfa其实就是bellmam_ford的优化。

bellmam-ford算法就看起来特别傻。——yxc

回想一下bellmam_ford,直接两重循环暴力(卡出奇迹)
那有些边更新是不一定会变小的。
如果我们优化一下……
SPFA来了
回忆一下前面的更新方式:

dist[b] = min(dist[b], dist[a] + w);

如果dist[a]变小了,dist[b]才一定会变小。
这就是SPFA的突破口
所以从这里开始优化。
具体思路是:
bfs
首先搞一个队列……

queue<int> q;

那这个队列是干蛤的呢?
存储所有变小的节点。
是否有一种似曾相识的感觉?
有就好了……继续……
然后每次更新点的时候判断一下是否小,小就更新。
当然st数组还是不能少帝~
结合如上叙述以及bellmam_ford的讲解,SPFA的板子就应该很弱了吧。
先初始化一下。

memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;

接着宽搜标准板子*INF

while(q.size())
{
    int t = q.front();
    q.pop();
    st[t] = false
}

边的遍历相信大家没忘。

for(int i = h[t]; i != -1; i = ne[i])
{
    int j = e[i];
}

接着看一下这个点需不需要更新,也是SPFA里最关键的部分。

if(dist[j] > dist[t] + w[i])
{
    dist[j] = dist[t] + w[i];
}

看一下是否在集合里,在就更新。

if(!st[j])
{
    st[j] = true;
    q.push(j);
}

最后康康有木有最短路。

if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];

完整の板子:

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

作者:cht
链接:https://www.acwing.com/activity/content/code/content/354290/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

为了证明是复制的,挂上上面四行。
好了看下板子题。
SPFA求最短路
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数n和m。

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

输出格式
输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出”impossible”。

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

输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2

有了SPFA,完事!
直接上代码了,也没啥可讲的。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, e[N], h[N], w[N], ne[N], idx, dist[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 ++;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a,b ,c;
        cin >> a>> b>> c;
        add(a, b, c);
    }
    int t = spfa();
    if(t == 0x3f3f3f3f) cout << "impossible";
    else cout << t;
}

当然如果出题人故意卡成了O(NM),请用堆优化Dijkstra。
QQ图片20200625161055.gif

SPFA的应用

第一章bellmam-ford的时候说过SPFA可以判断负欢负环。
这里讲一下。
先来看一下题目:
SPFA判断负环
给定一个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

来讲一下这道题。
dist[j]表示的是1->j的最短距离。
同时记录另一个东西:cnt数组。
cnt[j]表示的是1->j的边的数量。
每一次这么更新:
首先dist数组:

dist[j] = dist[t] + w[i];

cnt数组是这样更新的:

cnt[j] = cnt[t] + 1;

为啥?
请看图:
批注 2020-07-05 193144.png
顺便说一句,这个字大家先忍忍,下周二手写板就到了。
我们继续。
如果其中有一次cnt[j] > n:
就说明从1->j经过了n条边
=> 就说明1->j经过了n+1个点。
=> 说明路径上至少两点相同
=> 存在环。
=> 一定会变小,所以环是负权
=> 存在负权边。
这就是SPFA判断负环的重中之重。
然后我们把板子实现一般就行了,这里直接上代码(有点累了,快500行了)。
注意这里初始化的时候要初始化掉所有点。
为啥?
因为负环不一定从1开始。
而且这里不用初始化dist数组了哦。

#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = N * 5;
int n, m, h[N], e[M], ne[M], w[M], idx, dist[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 spfa()
{
    queue<int> q;
    for(int i = 1; i <= n; i ++)
    {
        st[i] = true;
        q.push(i);//初始化所有点
    }
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];//更新dist
                cnt[j] = cnt[t] + 1;//更新cnt
                if(cnt[j] >= n) return true;//如果cnt[j] >= n,根据上面的推理说明存在负环
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}

好了今天的分享就到这里了。有点累不留作业了。

这里是我的全部分享

下期见,bye~

(500行,好累,下一期说几道bfs,是个视频课没有文字,大家等着吧)



新鲜事 原文

cht
7小时前
窝来更新辣!


新鲜事 原文

cht
13小时前
y总啥时候能更新AC CHAT呢?


新鲜事 原文

cht
21小时前
今天下午考完语文就能更分享了 好开森 快两周没搞Oi了 会不会几个数学模型都忘光了呢 qwq


新鲜事 原文

cht
2天前
最后1天期末考 考完分享就来啦 大家再等一等!!!!



新鲜事 原文

cht
2天前
我们正在见证历史,见证ACWING是如何成为世界上最腻害的OJ的历史! 奥利给!


新鲜事 原文

cht
2天前
期末复习本的名字叫《欺魔砖庸本》 上天保佑明后天考试不要凉啊啊啊…… 下面内容划掉(据说不支持Markdown) (要是考的真的不好好后悔一直搞whk,状压DP都好几天了还是木有学会,分享1week没更) 我自闭了。 不过已经在写了, 暑假很快就能出。 有图为证: 去复习了,上天保佑。
图片


新鲜事 原文

cht
3天前
y总NB!加油!已经有框架了。
图片


题目讨论 AcWing 2039. emm

cht
4天前

农名是神马鬼




cht
4天前

如题。