【题目来源】https://www.luogu.com.cn/problem/P3385【题目描述】给定一个 n 个点的有向图请求出图中是否存在从顶点 1 出发能到达的负环。负环的定义是一条边权之和为负数的回路。【输入格式】本题单测试点有多组测试数据。输入的第一行是一个整数 T表示测试数据的组数。对于每组数据的格式如下第一行有两个整数分别表示图的点数 n 和接下来给出边信息的条数 m。接下来 m 行每行三个整数 u,v,w。1若 w≥0则表示存在一条从 u 至 v 边权为 w 的边还存在一条从 v 至 u 边权为 w 的边。2若 w0则只表示存在一条从 u 至 v 边权为 w 的边。【输出格式】对于每组数据输出一行一个字符串若所求负环存在则输出 YES否则输出 NO。【输入样例】23 41 2 21 3 42 3 13 1 -33 31 2 32 3 43 1 -8【输出样例】NOYES【数据范围】对于全部的测试点保证1≤n≤2×10^31≤m≤3×10^3。1≤u,v≤n−10^4≤w≤10^4。1≤T≤10。​​​​​​​【算法分析】● 请注意m 不是图的边数。● 简单版的利用 SPFA 判断负环问题详见https://blog.csdn.net/hnjzsyjyj/article/details/138470784● SPFA 算法1SPFA 算法即最短路径快速算法是基于 Bellman-Ford 算法优化而来的单源最短路径算法适用于带负权边、无负权环的有向图或无向图在算法竞赛中应用广泛。2SPFA 算法借助队列对 Bellman-Ford 算法进行优化仅将松弛成功、距离被更新的节点入队只处理存在更新潜力的节点减少冗余运算。3在 CSP/NOIP 等算法竞赛中遇到负权图优先选用 SPFA 算法求最短路径若图无负权边推荐堆优化 Dijkstra求最短路径。● SPFA 算法核心流程1初始化距离数组 dist[]。设 dist[s] 代表起点 s 到各点的最短距离先将起点距离置为 0其余节点初始化为无穷大。同时创建队列保存被松弛更新成功的待处理节点并借助 st[] 数组标记节点入队状态以此避免节点重复入队减少冗余计算。2循环取出队首节点 u遍历 u 的全部邻边 u→v。若满足松弛条件 dist[v]dist[u]w(u,v)则更新 dist[v]如果本次松弛成功且节点 v 不在队列中就将 v 入队。持续迭代直到队列为空。3队列为空算法结束。若任意节点入队次数≥节点总数 n说明图中存在负环。​​​​​​​【算法代码】#include bits/stdc.h using namespace std; const int N2e35; const int M3e35; int val[M1],e[M1],ne[M1],h[N],idx; int dis[N],cnt[N]; bool st[N]; int n,m; void add(int a,int b,int w) { val[idx]w,e[idx]b,ne[idx]h[a],h[a]idx; } int spfa() { queueint Q; memset(dis,0x3f,sizeof dis); memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); dis[1]0; Q.push(1); st[1]true; while(!Q.empty()) { int tQ.front(); Q.pop(); st[t]false; for(int ih[t]; i!-1; ine[i]) { int je[i]; if(dis[j]dis[t]val[i]) { dis[j]dis[t]val[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() { int T; cinT; while(T--) { cinnm; idx0; memset(h,-1,sizeof h); while(m--) { int a,b,c; cinabc; if(c0) { add(a,b,c); add(b,a,c); } else add(a,b,c); } if(spfa()) coutYES\n; else coutNO\n; } return 0; } /* in: 2 3 4 1 2 2 1 3 4 2 3 1 3 1 -3 3 3 1 2 3 2 3 4 3 1 -8 out: NO YES */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/138470784