Bellman-Ford算法:以边为研究对象, 每条边最多被松弛n-1次

void Bellman_Ford(int s)
{
    memset(d, 0x3f, sizeof d);

    d[s] = 0;

    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
            if (d[g[i].b] > d[g[j].a] + g[j].w)
                d[g[i].b] = d[g[i].a] + g[i].w;
}

优化:SPFA

void spfa(int s)
{
    memset(d, 0x3f, sizeof d);

    d[s] = 0;

    queue<int> q;
    q.push(s);

    st[s] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

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

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

应用:

最短路

P3371 【模板】单源最短路径（弱化版）

负环:边权和为负数的环(正权边有环图没有最长路)

P3385 【模板】负环

例题:

P2648 赚钱

1. 有统一点权D, 边权有两类, 边权0, 非0, 有向边;

2. 跑正环, 以及最长路, 也可以边权乘以-1后跑最短路和负环;

3. 没有指定起点, 建虚拟起点c+1, 向其余c个点连边, 边权为0

4. 创建虚拟点后, 总点数为c+1, 特判注意条件

#include <bits/stdc++.h>
using namespace std;

const int N = 210, M = 910, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int d[N], cnt[N];
int D, p, c, f, res;

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

int spfa()
{
    memset(d, 0xcf, sizeof d);

    queue<int> q;

    q.push(c + 1);

    st[c + 1] = true;
    d[c + 1] = 0; 

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d[j] < d[t] - w[i] + D)
            {
                d[j] = d[t] - w[i] + D;

                if (cnt[j] >= c) return -1;

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

    for (int i = 1; i <= c; i++) res = max(res, d[i]);

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> D >> p >> c >> f;

    memset(h, -1, sizeof h);

    int a, b, w;
    while (p--)
    {
        cin >> a >> b;

        add(a, b, 0);
    }

    while (f--)
    {
        cin >> a >> b >> w;

        add(a, b, w);
    }

    for (int i = 1; i <= c; i++) add(c + 1, i, 0);

    if (~spfa()) cout << res;
    else cout << "orz";


    return 0;
}

P2850 [USACO06DEC] Wormholes G

小小板子题

#include <bits/stdc++.h>
using namespace std;

const int N = 510, M = 5210;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int d[N], cnt[N];
int n, m1, m2;

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

bool spfa()
{
    memset(d, 0, sizeof d);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);

    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            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;

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

    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
    {
        cin >> n >> m1 >> m2;

        idx = 0;
        memset(h, -1, sizeof h);

        int a, b, c;
        for (int i = 0; i < m1; i++)
        {
            cin >> a >> b >> c;

            add(a, b, c);
            add(b, a, c);
        }

        for (int i = 0; i < m2; i++)
        {
            cin >> a >> b >> c;

            add(a, b, -c);
        }

        if (spfa()) cout << "YES\n";
        else cout << "NO\n";
    }


    return 0;
}

[ABC137E] Coins Respawn

1. 有一个与n连通的正环, -1;

2. 每条边的边权为c[i]-p;

3. 如何检查正环与n连通?

方法1: 给每个点染色, 环的颜色要与n一致;

方法2: 跑反图, 从n开始标记能到达的点, 再从点1跑

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 2510, M = 1e4 + 10;
ll h[N], e[M], w[M], ne[M], idx;
vector<int> g[N];
bool St[N], st[N];
ll d[N], cnt[N];
ll n, m, p;

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

bool spfa()
{
    memset(d, 0xcf, sizeof d);

    queue<int> q;

    q.push(1);

    d[1] = 0;
    st[1] = true;

    while(q.size())
    {
        ll t = q.front();
        q.pop();

        st[t] = false;

        for (ll i = h[t]; ~i; i = ne[i])
        {
            ll j = e[i];

            if (St[j] && d[j] < d[t] + w[i] - p)
            {
                d[j] = d[t] + w[i] - p;
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;

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

    return false;
}

void dfs(int u)
{
    if (St[u]) return;

    St[u] = true;

    for (auto i : g[u]) dfs(i);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> p;

    memset(h, -1, sizeof h);

    ll a, b, c;
    while (m--)
    {
        cin >> a >> b >> c;

        add(a, b, c);
        g[b].push_back(a);
    }

    dfs(n);

    if (spfa()) cout << -1;
    else cout << max(0ll, d[n]);


    return 0;
}