Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 23 24 25 26 27 28 29 >> Отображать по:
#1329
Кладоискатель
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\)). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).

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

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

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

Первая строка содержит 2 числа \(N\) и \(M\), задающие размеры лабиринта. Далее следует описание лабиринта: \(N\) строк по \(M\) символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).

В \((N+2)\)-й строке находится число \(K\) (\(1 \le K \le N \times M\)) -- количество входов в лабиринт. Далее в \(K\) строках содержатся координаты входов. Так, в \(i\)-й строке содержатся числа \(x_i\) и \(y_i\), означающие,что \(i\)-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце (\(1 \le x_i \le N, 1 \le y_i \le M\)). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

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

Примеры
Входные данные
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
Выходные данные
1
Входные данные
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
Выходные данные
-1
#1330
Маршрут кладоискателя
  

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\))), в одной клетке которого находится клад, в \(K\) клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

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

Первая строка содержит 2 числа \(N <= 100\) и \(M <= 100\), задающие размеры лабиринта. Далее следует описание лабиринта: \(N\) строк по \(M\) символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).

В \((N+2)\)-й строке находится число \(K\) (\(1 \le K \le N \times M\)) -- количество входов в лабиринт. Далее в \(K\) строках содержатся координаты входов. Так, в \(i\)-й строке содержатся числа \(x_i\) и \(y_i\), означающие,что \(i\)-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце (\(1 \le x_i \le N, 1 \le y_i \le M\)). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

В первой строке вывести одно число - длину кратчайшего маршрута. В следующих строках необходимо вывести кратчайший маршрут. Каждую клетку маршрута (включая начальную и конечную) вывести на отдельной строке в формате \(x_i\) \(y_i\), где \(x_i\) - строка клетки, а \(y_i\) - столбец клетки.

Если существует несколько путей минимальной длины, выведите любой. Если до сокровища невозможно добраться, в единственной строке выведите -1.

Примеры
Входные данные
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
Выходные данные
4
Входные данные
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
Выходные данные
-1
#1332
Транзитивное замыкание
  

Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в \(i\)-й строке и \(j\)-м столбце находится 1, если от вершины \(i\) можно добраться до вершины \(j\), и 0 - иначе.

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

В первой строке дано число \(N\) (\(1 \le N \le 100\)) - число вершин в графе. Далее задана матрица смежности графа: в \(N\) строках даны по \(N\) чисел 0 или 1 в каждой. \(i\)-е число в \(i\)-й строке всегда равно 1.

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

Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.

Примеры
Входные данные
4
1 1 0 0
0 1 1 0
1 0 1 0
0 0 1 1
Выходные данные
1 1 1 0 
1 1 1 0 
1 1 1 0 
1 1 1 1
#1333
Долой списывание!
  

Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.

У профессора записаны все пары студентов, обменявшихся записками. Требуется определить, сможет ли он разделить студентов на две группы так, чтобы любой обмен записками осуществлялся от студента одной группы студенту другой группы.

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

В первой строке находятся два числа \(N\) и \(M\) - количество студентов и количество пар студентов, обменивающихся записками (\(1 \le N \le 100\), \(0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

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

Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Примеры
Входные данные
3 2
1 2
2 3
Выходные данные
YES
Входные данные
3 3
1 2
2 3
1 3
Выходные данные
NO
#1334
Два профессора
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Профессор Флойд и профессор Дейкстра ненавидят друг друга. После переезда университета во вновь отстроенный университетский городок они потребовали себе кабинеты в зданиях, максимально удалённых друг от друга. Вам поручено найти расстояние между двумя такими зданиями.

Иными словами, требуется найти два здания, кратчайший путь между которыми наибольший среди всех пар зданий, и вывести длину этого пути. Так как профессорам иногда все же нужно встречаться, путь между выбранными зданиями должен существовать.

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

В первой строке находятся два числа \(N\) и \(M\) - количество зданий и количество дорог, соединяющих здания (\(1 \le N \le 100, 0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i\), \(e_i\), \(l_i\) - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (\(1 \le s_i, e_i \le N, 0 \le l_i \le 100\), дороги двунаправленные).

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

Необходимо вывести одно число - искомое расстояние.

Примеры
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
3
Входные данные
3 0
Выходные данные
0
Страница: << 23 24 25 26 27 28 29 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест