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

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Надо найти две вершины, кратчайший путь между которыми имеет наибольшую длину.

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

В первой строке задано число вершин N ≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от от 0 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.

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

Выведите одно число – длину искомого пути.

Примеры
Входные данные
3
0 7 3
7 0 10
2 215 0
Выходные данные
10
#97
Самый короткий путь
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю).

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

В первой строке задано число вершин N≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от -1000000 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.

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

Выведите одно число – искомый минимум. Если его не существует, выведите  -1.

Примеры
Входные данные
3
0 42 18468 
6335 0 26501 
19170 15725 0
Выходные данные
42
Входные данные
3
0 -7 3
-2 0 10
2 215 0
Выходные данные
-1
#98
Есть ли цикл?
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры
Входные данные
3
0 1 0
0 0 1
0 0 0
Выходные данные
0
Входные данные
3
0 1 0
0 0 1
1 0 0
Выходные данные
1
#160
Путь
  
Максимальное время работы на одном тесте:   5 секунд

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

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

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

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

Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.

Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.

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

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

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

На вход программы поступает  пять чисел: N, x1, y1, x2, y2 (5 <= N <= 20, 1 <= x1, y1, x2, y2 <= N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

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

В первой строке выведите единственное число K - наименьшее необходимое число ходов коня. В каждой из следующих K+1 строк должно быть записано 2 числа - координаты очередной клетки в пути коня.

Пример выходного файла ниже неполный, правильный пример такой:

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