P3385 【模板】负环

    • 2.5K通过
    • 11K提交
  • 题目提供者 HOOCCOOH
  • 评测方式 云端评测
  • 标签 图论 负权环 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索

    输入输出格式

    输入格式:

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

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

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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
    
    输出样例#1: 复制
    N0
    YE5
    

    说明

    $$n\leq 2000$$ $$m\leq 3000$$ $$-10000\leq w\leq 10000$$ $$T\leq 10$$ 建议复制输出格式中的字符串。 本题数据感谢@negiizhao的精心构造,请不要使用玄学算法 本题数据有更新

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。