专栏文章

题解：P3385 【模板】负环

GGs_The_Wolrd
P3385题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miphhnyy
此快照首次捕获于
2025/12/03 12:05
3 个月前
此快照最后确认于
2025/12/03 12:05
3 个月前
查看原文

P3385 【模板】负环 题解

题意

判断是否有以 11 为起点能达到的负环。
负环的定义是：环上所有权值加起来为负数。

题目分析

为什么要找负环？

例如下面一张图就可以很好的解释负环。
根据 SPFA⁡\operatorname{SPFA} 从 11 开始，假如我们向节点 33 走。
走一圈回来发现是 −1-1。如果我们在这个环上越走越久，最短路就越来越小，妨碍我们跑最短路。

算法分析

这里使用 SPFA⁡\operatorname{SPFA} 判断负环。我们知道，最短路中有一个松弛操作的概念，即为
在一个有 nn 个节点的图中判断最短路，每个节点至多走 n−1n - 1 次。
所以当我们每走一个点就记录走了多少次，当走的次数 ≥n\geq n 时就是负环。

AC Code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...