Problem

7 /10


Chu kỳ tiêu cực-2

Theory Click to read/hide

bạn có thể đọc thêm về cách tìm chu kỳ âm tại đây: http://e-maxx.ru/algo/export_ford_bellman

Problem

Cho một đồ thị có hướng. Xác định xem nó có chu kỳ trọng số âm hay không và nếu có, hãy xuất ra nó.
 
Đầu vào
Dòng đầu tiên chứa số N (1 <= N <= 100) – số đỉnh của đồ thị. N dòng tiếp theo chứa N số, mỗi dòng – ma trận kề đồ thị. Trọng số của cạnh theo modulo nhỏ hơn 100000. Nếu không có cạnh nào, giá trị tương ứng là 100000.
 
Đầu ra
Trên dòng đầu tiên in "CÓ" nếu chu kỳ tồn tại hoặc "KHÔNG" nếu không. Nếu có một vòng lặp, trong dòng thứ hai in số lượng đỉnh trong đó (đếm cùng – đầu tiên và cuối cùng), và trong dòng thứ ba – các đỉnh bao gồm trong chu trình này theo thứ tự đi qua. Nếu có nhiều chu kỳ thì  in bất kỳ trong số chúng.

Ví dụ <đầu>

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!

# Đầu vào Đầu ra
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
CÓ
4
3 2 1 3