Courses

グラフ理論

フロイドのアルゴリズム

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」を出力します。ループがある場合は、2 行目にその中の頂点の数を出力し (同じ – 最初と最後を数えます)、3 行目に – を出力します。このサイクルに含まれる頂点はトラバーサル順です。複数のサイクルがある場合は、それらのいずれかを印刷します。

例 <頭> <本体>

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