P3385 【模板】负环 题解

_Elysia_ · 2023-01-13 18:40:39 · 个人记录

题目传送门

题意：

负环的定义：若图中存在一个环，环上各边的边权和为负数，则称该环为负环。

分析：

含有负环的图显然是没有最短路的，因为每走一圈这个负环，总权值就会更小，最后一直循环，导致陷在环里出不来。

注意：会看题目，数据中不只是m条边，最多可以有2m条边，边数组一定要开大。

因此，我们可以用 Bellman-Ford 或 SPFA 来判断负环。

（从某种意义上来将 SPFA 基本上可以取代 Bellman-Ford。所以本题解就不展开来讲Bellman-Ford了。）

_补：

缺点：本方法效率不高，如果数据使得n个点在最后返回前都被访问n次,那么本程序的效率将会变得很低。那么如何进行简单的优化呢?且看方法二。

方法二：

众所周知，若图中没有负环，则从源点到达除源点外的另一个节点的路径最多包含n（就像链一样）。若某个路径经过超过 n 个节点，则图中有负环。

*该方法避免了方法一的最坏情况，大大提高了判断负环的效率，虽理论上时间复杂度一样，但实际上方法二是优于方法一的。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 6e3 + 20, inf = 1e16 + 20;
ll T, n, m, u, v, w, s = 1;
ll cnt = 0, h[N], nxt[N], val[N], to[N];
ll vis[N], dis[N];
bool flag[N];
queue<ll> q;
void add_edge(ll u, ll v, ll w) {
    to[++cnt] = v;
    val[cnt]  = w;
    nxt[cnt]  = h[u];
    h[u]      = cnt;
}
void init(){
    memset(to, 0, sizeof(to));
    memset(val, 0, sizeof(val));
    memset(h, 0, sizeof(h));
    memset(nxt, 0, sizeof(nxt));
    memset(flag, 0, sizeof(flag));
    memset(vis, 0, sizeof(vis));
    cnt = 0;
    for(int i = 1; i <= n; i++) dis[i] = inf;
    dis[s] = 0;
    while(!q.empty()) q.pop();

}
bool SPFA(ll s) {
    q.push(s);
    vis[s] = flag[s] = 1;
    while(!q.empty()){
        ll u = q.front();
        q.pop();
        flag[u] = 0;

        for(int i = h[u]; i; i = nxt[i]){
            ll v = to[i];
            if(dis[v] > dis[u] + val[i]) {
                dis[v] = dis[u] + val[i];
                vis[v] = vis[u] + 1;
                if(vis[u] > n) return 1;//判断负环
                if(flag[v] == 0) {
                    q.push(v);
                    flag[v] = 1;
                }
            }
        }
    }
    return 0;
}
int main (){
    scanf("%lld", &T);
    while(T--) {
        scanf("%lld%lld", &n, &m);
        init();
        for(int i = 1; i <= m; i++) {
            scanf("%lld%lld%lld", &u, &v, &w);
            if(w >= 0) {
                add_edge(u, v, w);
                add_edge(v, u, w);
            }
            else add_edge(u, v, w);
        }
        if(SPFA(s) == 1) printf("YES\n");
        else             printf("NO\n");

    }
    return 0;
}

测评用时 571ms