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" چاپ کنید. در صورت وجود حلقه، در خط دوم تعداد رئوس موجود در آن (با شمارش همان &ndash؛ اول و آخر) و در خط سوم – رئوس موجود در این چرخه به ترتیب پیمایش هستند. اگر چندین چرخه وجود دارد،  هر یک از آنها را چاپ کنید.

نمونه‌ها <سر> <بدن>
# ورودی خروجی
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
بله
4
3 2 1 3

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!