Skip to content

1344: Negative cycle

题目

题目描述

给一个 $n (1\leq n \leq 2500)$ 个点 $m(1\leq m\leq 6200)$ 条边的有向图,边权可能为负。

你需要判断图中是否存在负环。如果有,请输出任意一个负环。

Input

请从 stdin 读入。

第一行为三个正整数 $n, m$。 第二行起 $m$ 行,每行三个非负整数 $u_i, v_i, w_i (-10^9 \leq w_i \leq 10 ^ 9)$,表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

对于 $30$ 分的数据,$m \leq 20$。

Output

请输出到 stdout 中。

  • 如果不存在负环,输出 No

  • 如果存在负环,请输出 Yes,并在第二行输出一个整数 $ k (1 \leq k \leq n)$ 表示你的负环中存在的顶点数,第三行为按照从某一个点出发经过的 $k$ 个顶点。

你的输出可以包含重复顶点,唯需保证 $1 \leq k \leq n$。如果存在一个负环与你的输出对应,那么你的输出就是正确的。

Sample Input

txt 1 1 1 1 -1

txt 3 3 1 2 1 2 3 2 3 1 -4

txt 3 3 1 2 1 2 3 2 3 1 -3

Sample Output

txt Yes 1 1

txt Yes 3 1 2 3

txt No

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!