华师一附中OI组

标题: P3385 【模板】负环 [打印本页]

作者: admin 时间: 2018-5-3 14:19
标题: P3385 【模板】负环
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的精心构造，请不要使用玄学算法本题数据有更新

欢迎光临华师一附中OI组 (http://hsyit.cn/)