Problem

7 /10


Cycle négatif-2

Theory Click to read/hide

vous pouvez en savoir plus sur la recherche d'un cycle négatif ici : http://e-maxx.ru/algo/export_ford_bellman

Problem

Étant donné un graphe orienté. Déterminez s'il a un cycle de poids négatif, et si c'est le cas, affichez-le.
 
Entrée
La première ligne contient le nombre N (1 <= N <= 100) – le nombre de sommets du graphe. Les N lignes suivantes contiennent N nombres chacune – matrice d'adjacence de graphe. Les poids des arêtes sont modulo inférieurs à 100 000. S'il n'y a pas d'arête, la valeur correspondante est 100 000.
 
Sortie
Sur la première ligne écrivez "OUI" si le cycle existe, ou "NON" sinon. S'il y a une boucle, imprimez sur la deuxième ligne le nombre de sommets qu'elle contient (en comptant le même – premier et dernier), et sur la troisième ligne – les sommets inclus dans ce cycle sont dans l'ordre de parcours. S'il y a plusieurs cycles, alors  imprimer l'un d'eux.

Exemples
3
100000 100000 -51
100  ; 100000 100000
100000 -50  100000
OUI
4
3 2 1 3
# Entrée Sortie
1

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!