题目描述

暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
以上貌似被毒瘤出题人卡了

输入输出格式

输入格式:

第一行一个正整数T表示数据组数,对于每组数据:

第一行两个正整数N M,表示图有N个顶点,M条边

接下来M行,每行三个整数a b w,表示a->b有一条权值为w的边(若w < 0则为单向,否则双向)

输出格式:

共T行。对于每组数据,存在负环则输出一行”YE5″(不含引号),否则输出一行”N0″(不含引号)。


dfs-spfa对于随机数据是非常快的
但是实际上是指数复杂度
然后上周被出题人卡了
实际上随机加边貌似能乱搞
然后今天又被卡了

所以稳定的还是bfs-spfa
具体的操作为每次松弛的时候记录一下次数
一个点入队列大于等于n次的就说明有负环

 

分类: 图论题解

说点什么

avatar
  Subscribe  
提醒