华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 996|回复: 0
打印 上一主题 下一主题

P3385 【模板】负环

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-5-3 14:19:11 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
https://www.luogu.org/problemnew/show/P3385
题目描述
暴力枚举/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 2000n≤2000
m\leq 3000m≤3000
-10000\leq w\leq 10000−10000≤w≤10000
T\leq 10T≤10
建议复制输出格式中的字符串。 本题数据感谢@negiizhao的精心构造,请不要使用玄学算法 本题数据有更新
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:37 , Processed in 0.199977 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表