P3385 负环

· · 题解

负环的定义是：一条边权之和为负数的回路。所以在负环的图上是不存在最短路的。

所以，我们考虑这样的思路：先试着求出 1 到其他点的最短路，如果发现不存在合法路径，就说明有负环存在。

求出任意两点之间的最短路，如果有一个点到自己的距离为负数，就说明存在负环，时间复杂度 O(TN^3)，（关于弗洛伊德：它死了）

开玩笑，开玩笑。其实正解就是 SPFA。

SPFA 本质上可以看作一个变形的 BFS，我们想想它的算法流程（参考了蓝书）：

  1. 用 dis_i 表示点 i 到起点的距离，初始值设为无穷大，起点设为 0，并把它放入一个队列中。

  2. 每次从队头取出点 x，扫描它所有的领居点 y，两点的距离为 z，如果 dis_x+z<dis_y，则更新 dis_y，同时如果 y 不在队列中则让 y 入队。

  3. 重复执行直到队空。

如果存在负环，那么就会有负边，这样的话有些点就会被一直更新。所以如果一个点被超 N 个点更新过，那就说明有负环。

或者，可以记录最短路的边数。如果不存在负环，图的最短路是不会反复经过一条边的。

更新次数判负环：

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring> 
using namespace std;
int T, n, m, u, v, w;
vector <pair<int, int> > G[2001];
int dis[2001], cnt[2001];
bool in[2001];
void spfa(){
    memset(dis, 0x3f3f, sizeof(dis));
    memset(in, 0, sizeof(in));
    memset(cnt, 0, sizeof(cnt));
    queue <int> q;
    q.push(1);
    dis[1] = 0;
    in[1] = true;
    cnt[1] = 1;
    while (!q.empty()){
        u = q.front();
        q.pop();
        in[u] = false;
        for (int i = 0; i < G[u].size(); i++){
            v = G[u][i].first;
            w = G[u][i].second;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if (!in[v]){
                    cnt[v]++;
                    q.push(v);
                    in[v] = true;
                    if (cnt[v] >= n){
                        printf("YES\n");
                        return;
                    } 
                }
            }
        }
    }
    printf("NO\n");
}
int main(){
    scanf("%d", &T);
    for (int  t = 0; t < T; t++){
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++){
            G[i].clear();
        }
        for (int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &w);
            G[u].push_back(make_pair(v, w));
            if (w >= 0){
                G[v].push_back(make_pair(u, w)); 
            } 
        }
        spfa();
    }
    return 0;
}

最短路路径数判负环：

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring> 
using namespace std;
int T, n, m, u, v, w;
vector <pair<int, int> > G[2001];
int dis[2001], cnt[2001], sum;
bool in[2001];
void spfa(){
    memset(dis, 0x3f3f, sizeof(dis));
    memset(in, 0, sizeof(in));
    memset(cnt, 0, sizeof(cnt));
    queue <int> q;
    q.push(1);
    dis[1] = 0;
    in[1] = true;
    cnt[1] = 0;
    while (!q.empty()){
        u = q.front();
        q.pop();
        in[u] = false;
        for (int i = 0; i < G[u].size(); i++){
            v = G[u][i].first;
            w = G[u][i].second;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= sum){
                    printf("YES\n");
                    return;
                }
                if (!in[v]){
                    q.push(v);
                    in[v] = true; 
                }
            }
        }
    }
    printf("NO\n");
}
int main(){
    scanf("%d", &T);
    for (int  t = 0; t < T; t++){
        scanf("%d%d", &n, &m);
        sum = 0;
        for (int i = 1; i <= n; i++){
            G[i].clear();
        }
        for (int i = 0; i < m; i++){
            scanf("%d%d%d", &u, &v, &w);
            G[u].push_back(make_pair(v, w));
            sum++;
            if (w >= 0){
                sum++;
                G[v].push_back(make_pair(u, w)); 
            } 
        }
        spfa();
    }
    return 0;
}