Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Отрицательный цикл

Алгоритм Флойда

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

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

Примеры
Входные данные Выходные данные
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
YES

Кладоискатель

Алгоритм Флойда

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера NM (1NM100 , NM100). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).
 
В одной из клеток находится клад, который и хочет достать Вася. В лабиринте есть K входов, из которых Вася может начать свой путь.
 
Требуется определить, с какого входа Васе нужно начать свой путь, чтобы пройденное расстояние до клада было наименьшим. Если таких входов несколько, нужно вывести вход с наименьшим номером.
 
Входные данные
Первая строка содержит 2 числа N и M, задающие размеры лабиринта. Далее следует описание лабиринта: N строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
 
В (N+2)-й строке находится число K (1<=K<= NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1xiN1yiM). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
 
Выходные данные
Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.

Примеры
Входные данные Выходные данные
1
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
1
2
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
-1

Отрицательный цикл-2

Алгоритм Флойда

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

Примеры
Входные данные Выходные данные
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
YES
4
3 2 1 3

Самый длинный путь

Алгоритм Флойда

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

Примеры
Входные данные Выходные данные
1
3
0 7 3
7 0 10
2 215 0
10
 

Есть ли цикл?

Обход в глубину Алгоритм Флойда

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

Примеры
Входные данные Выходные данные
1
3
0 1 0
0 0 1
0 0 0
0
2
3
0 1 0
0 0 1
1 0 0
1

Флойд - существование

Алгоритм Флойда

Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует ли кратчайший путь между ними или нет.
 
Комментарий: Кратчайший путь может не существовать по двум причинам:
  • Нет ни одного пути
  • Есть пути сколь угодно маленького веса
     
Входные данные
В первой строке входного файла записано единственное число: N (1 <=N <=100) — количество вершин графа. В следующих N строках по N чисел — матрица смежности графа (j-е число в i-й строке соответствует весу ребра из вершины i в вершину j): число 0 обозначает отсутствие ребра, а любое другое число — наличие ребра соответствующего веса. Все числа по модулю не превышают 100.
 
Выходные данные
Выведите N строк по N чисел. j-е число в i-й строке должно соответствовать кратчайшему пути из вершины i в вершину j. Число должно быть равно 0, если пути не существует, 1, если существует кратчайший путь, и 2, если пути существуют, но бывают пути сколь угодно маленького веса.

Примеры
Входные данные Выходные данные
1
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 -1
0 0 0 -1 0 
1 1 1 0 0 
1 1 1 0 0 
1 1 1 0 0 
0 0 0 2 2 
0 0 0 2 2 

Самый короткий путь

Алгоритм Флойда

Дан ориентированный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю, стремящийся к бесконечности).
 
Входные данные
В первой строке задано число вершин N≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от -1000000 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.
 
Выходные данные
Выведите одно число – искомый минимум. Если его не существует, выведите  -1.
Примеры
Входные данные Выходные данные
1
3
0 42 18468 
6335 0 26501 
19170 15725 0 
42
2
3
0 -7 3
-2 0 10
2 215 0 
-1

Запросы по Флойду

Алгоритм Флойда

Дан неориентированный взвешенный граф с отрицательными весами, необходимо выдавать информацию о кратчайшем пути между 2 вершинами.
 
Входные данные:
В первой строчке дано целое число n - количество вершин в графе.
Дальше на вход подается матрица смежности, в которой -1 означает отсутсвие ребра между вершинами.
После матрицы идет число k - количество запросов, в следующих k строках содержится по 2 числа а и b - вершины в запросе.
 
Выходные данные:
В строке должно содержаться k чисел - расстояние между парой чисел из запроса в порядке  их ввода, если нельзя добраться из вершины a в вершину b, следует вывести Imp.
 
Примеры
Входные данные Выходные данные
1
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
7
4
3

(с) Свиридов Ярослав

Космическое путешествие

Алгоритм Флойда

В MMORPG "Космические торговцы online" скорость перемещения игрока между звёздами ограничена одним парсеком в секунду. С такой скоростью можно быстро добраться до ближайших звёзд, но на путешествие с одного края галактики до другого может потребоваться несколько часов. Для ускорения таких долгих путешествий создатели игры сделали несколько "кротовых нор" — туннелей, соединяющих две точки в пространстве, которые позволяют мгновенно перемещаться между этими точками туда и обратно.

Напишите программу, которая вычисляет минимальное время путешествия, используя информацию о "кротовых норах".

В первой строке ввода содержится целое число N (1 ≤ N ≤ 100). Далее следует строка, содержащая 6 целых чисел — координаты начальной (xs,ys,zs) и конечной (xt,yt,zt) точки путешествия. Далее следует N строк, содержащих 6 целых чисел — координаты концов "кротовых нор". Все координаты измеряются в парсеках и находятся в диапазоне от 0 до 10000, и нет точек с совпадающими координатами.

Вывести минимальное время путешествия в секундах с точностью не менее 10−6.
Примеры
Входные данные Выходные данные
1
1
0 0 0 100 100 0
1 1 1 50 100 10
52.722246