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"를 인쇄하십시오. 루프가 있는 경우 두 번째 줄에 정점 수를 인쇄하고(동일한 – 첫 번째 및 마지막 계산) 세 번째 줄에 – 이 주기에 포함된 정점은 순회 순서입니다. 주기가 여러 개인 경우 아무거나 출력하세요.

예 <헤드> <일># <몸>

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