Module: 弗洛伊德算法


Problem

7 /10


负循环 2

Theory Click to read/hide

你可以在这里阅读更多关于寻找负循环的信息：http://e-maxx.ru/algo/export_ford_bellman

Problem

给定一个有向图。判断是否有负权重循环，如果有则输出。
 
输入
第一行包含数字 N (1 <= N <= 100) –图的顶点数。接下来的 N 行每行包含 N 个数字——图邻接矩阵。小于100000的边权重取模，如果没有边，对应的值为100000。
 
输出
如果循环存在则在第一行打印“YES”，否则打印“NO”。如果有一个循环，在第二行打印其中的顶点数（计算相同的 - 第一个和最后一个），并在第三行 -此循环中包含的顶点按遍历顺序排列。如果有几个循环，那么 打印其中任何一个。

例子 <头> <日># <正文>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

输入 输出
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
是
4
3 2 1 3