Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
#178
Форд-Беллман
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

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

Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).

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

Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Примеры
Входные данные
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
Выходные данные
0 10 20 30000 30000 30000
#179
Лабиринт знаний
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход – в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

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

Первая строка входных данных содержит целые числа N (1 <= N <= 2000) – количество комнат и M (1 <= M <= 10000) – количество дверей. В каждой из следующих M строк содержится описание двери – номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.

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

Выведите ":)" – если можно получить неограниченно большой запас знаний, ":(" – если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.

Примеры
Входные данные
2 2
1 2 3
1 2 7
Выходные данные
7
#180
Цикл
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
3
100000 100000 -51
100  100000 100000
100000 -50  100000
Выходные данные
YES
4
3 2 1 3
#181
Дерево?
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Максимальное время работы на одном тесте: 5 секунд

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

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

Сначала вводится число N – количество вершин графа (от 1 до 100). Далее записана матрица смежности размером N*N, в которой 1 обозначает наличие ребра, 0 – его отсутствие. Матрица симметрична относительно главной диагонали.

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

Введите сообщение YES, если граф является деревом, и NO в противном случае.

Примеры
Входные данные
4
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0
Выходные данные
YES
#182
Получи дерево
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Максимальное время работы на одном тесте: 1 секунда

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

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

Сначала вводятся два числа: N (от 1 до 100) и M – количество вершин и ребер графа соответственно. Далее идет M пар чисел, задающих ребра. Гарантируется, что граф связный.

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

Выведите N-1 пару чисел – ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Примеры
Входные данные
4 4
1 2
2 3
3 4
4 1
Выходные данные
1 2
2 3
3 4
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест