АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

788. Цикл

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Дан взвешенный ориентированный граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

Входные данные.

В первой строке входных данных записано число N (1≤N≤100) - количество вершин графа. В следующих N строках находится по N чисел - матрица смежности графа. Все веса ребер не превышают по модулю 10000. Если ребра нет, то соответствующее число равно 100000.

Выходные данные.

В первой строке выведите "YES", если цикл существует, или "NO" в противном случае. При наличии цикла выведите во второй строке количество вершин в искомом цикле (считая одинаковые первую и последнюю), и в третьей строке - вершины, входящие в этот цикл в порядке обхода.

Пример входных данных:

2
0 -1
-1 0

Пример выходных данных:

YES
3
1 2 1

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Учебные курсы / Задачи с olympiads.ru /
787. 263 - Лабиринт знаний 788. 789. 265 - Табличка 790. 266 - Два коня 791. 267 - Дерево?
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Графы /
779. 10 - Заправки 788. 1970. 12 - Автобусы 9. 13 - Сеть
 
время генерации 0.11 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.