什么是SPFA

SPFA是在Bellman-Ford的基础上进行的一种优化，Bellman-Ford的思路是进行n-1次循环，每次循环都遍历每一条边来更新最短路，复杂度是 $O(n*m)$，不难发现每次遍历边(u-v)去更新dis[v]时，当且仅当dis[u]被更新过后才会更新dis[v],所以我们可以用个队列，存下来被修改过的点的id，挨个去更新，为了防止进一步优化，我们开一个vis数组，初始化都是0，在队列内则vis赋1，只有当dis能更短，且v不在队列内时才塞入，这样的思路就是SPFA
他与迪杰斯特拉的区别是，迪杰斯特拉不处理负权边，所以是个贪心，每个点只会更新一次dis，而SPFA会处理负权边，每个点可能因此更新很多次

板子

bool vis[MAX];
int dis[MAX];

void spfa(){
    queue<int>q;
    q.push(1);
    mem(dis, inf);//初始化dis数组
    vis[1] = 1;//初始化源点
    dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();
        vis[u] = 0;//扔出队列了就赋0
        for(int i = head[u]; i; i = tr[i].nex){//用u去更新v点
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                if(!vis[v]){//只有不在队列里面才塞进去
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    if(dis[n] == inf)cout << "impossible" << endl;
    else cout << dis[n] << endl;
}

SPFA如何判负环

Bellman-Ford判环的思路很简单，再跑完n-1次循环后再跑一次，看有没有点能继续更新最短路，有的话就说明存在负环

SPFA和它的道理是一样的，都是图上任意两个点直接的最短路的长度绝对会 < n,所以我们只需要维护一个cnt数组，表示起点到i的最短路的长度，当任意一个cnt[i] >= n时，说明出现了负环

注意，只判环时，dis数组无需初始化

板子

bool vis[MAX];
int dis[MAX];
int cnt[MAX];

void spfa(){
    queue<int>q;
    for(int i = 1; i <= n; ++i){//初始化，这里的是判断无起点类的图，如果有题目有起点，就只将源点塞入，并更新vis值
        q.push(i);
        vis[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front();q.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                cnt[v] = cnt[u] + 1;//更新边数
                if(cnt[v] >= n){
                    cout << "Yes\n";
                    return;
                }
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    cout << "No\n";
}

SPFA如何判正环

和判负环一样，只需要在更新最短路时改成更新最长路即可，同样不需要初始化dis数组，只有在题目需要的时候再更新

例题：POJ – 1860

题目描述：

城市有n个货币兑换点，每个货币兑换点只针对两种货币的互相兑换，每种兑换都有一个独有的汇率和佣金，假设你手上有x的货币a,在汇率为p,佣金为c的情况下可以换成货币b，则可以得到 (x-a) * p的货币b,现在你仅有一个初始货币s,数量是v,你可以通过无数次兑换，问你能不能通过货币兑换的方式来盈利

思路：

如题目所描述的进行建图，判断图中有没有能包含源点s的正环

使用SPFA来解决

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, s;
double v;
int a, b;
double hui[105][105];
double yong[105][105];
vector<int>tr[105];

bool vis[MAX];
double dis[MAX];
int cnt[MAX];
void SPFA(){
    queue<int>q;
    q.push(s);
    mem(dis, 0);
    dis[s] = v;
    vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();q.pop();
        vis[u] = 0;
        for(int i = 0; i < tr[u].size(); ++i){
            int v = tr[u][i];
            if(dis[v] < (dis[u] - yong[u][v]) * hui[u][v]){
                dis[v] = (dis[u] - yong[u][v]) * hui[u][v];
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n){
                    cout << "YES\n";
                    return;
                }
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    cout << "NO\n";
}

void work(){
    cin >> n >> m >> s >> v;
    for(int i = 1; i <= m; ++i){
        cin >> a >> b;
        cin >> hui[a][b] >> yong[a][b] >> hui[b][a] >> yong[b][a];
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    SPFA();
}


int main(){
    io;
    work();
    return 0;
}