题解：P3385 【模板】负环

· · 题解

P3385 【模板】负环 题解

题意

判断是否有以 1 为起点能达到的负环。

负环的定义是：环上所有权值加起来为负数。

题目分析

为什么要找负环？

例如下面一张图就可以很好的解释负环。

根据 \operatorname{SPFA} 从 1 开始，假如我们向节点 3 走。

走一圈回来发现是 -1。如果我们在这个环上越走越久，最短路就越来越小，妨碍我们跑最短路。

算法分析

这里使用 \operatorname{SPFA} 判断负环。我们知道，最短路中有一个松弛操作的概念，即为

在一个有 n 个节点的图中判断最短路，每个节点至多走 n - 1 次。

所以当我们每走一个点就记录走了多少次，当走的次数 \geq n 时就是负环。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10,INF = 0x3f3f3f3f;
int T;
int n,m;
int dis[maxn];
int cnt[maxn];
struct node 
{
    int v;
    int w;
};
vector<node> g[maxn];
queue<int> q;
int x,y,z;
bool SPFA(int x) //某个已死算法定义bool类型用于判断负环
{
    dis[x] = 0;
    q.push(x);
    while(q.size())
    {
        int u = q.front();q.pop();
        for(auto i:g[u])
        {
            int nv = i.v;
            int nw = i.w;
            if(dis[nv] > dis[u] + nw)
            {

                dis[nv] = dis[u] + nw;
                if(++ cnt[nv] >= n) return 1; //是负环
                q.push(nv);
            }
        }
    }
    return 0;
}
void solve()
{
    memset(dis,0x3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(z >= 0) g[x].push_back({y,z}),g[y].push_back({x,z});
        else g[x].push_back({y,z});
      //存图 只有正数才存双向边
    }
    puts(SPFA(1)?"YES":"NO");
}
int main()
{
    scanf("%d",&T);
    while(T --)
    {
        for(int i=1;i<=n;i++) g[i].clear(); //初始化邻接表
        solve();
    }
    return 0;
}