Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 42 43 44 45 46 47 48 >> Отображать по:
#3494
Алгоритм Дейкстры за $M$~log$N$
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.

Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.

Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.

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

Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).

Примеры
Входные данные
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1
Выходные данные
18 0 5 2 8
#3555
10E: Pink Floyd
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Найти самый длинный путь от одной вершины до другой в ориентрованном графе, либо определить, что существует сколь угодно длинный путь, либо определить, что пути не существует.

Группа Pink Floyd собирается отправиться в новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других — много ест и набирает вес.

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

Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла содержит три натуральных числа \(n\), \(m\) и \(k\) — количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (\(n \le 100\), \(m \le 10\,000\), \(2 \le k \le 10\,000\)). Города пронумерованы числами от \(1\) до \(n\).

Следующие \(m\) строк содержат описание рейсов, по одному на строке. Рейс номер \(i\) описывается тремя числами \(b_i\), \(e_i\) и \(w_i\) — номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (\(1 \le b_i, e_i \le n\), \(-100\,000 \le w_i \le 100\,000\)).

Последняя строка содержит числа \(a_1, a_2, ..., a_k\) — номера городов, в которых проводятся концерты (\(a_i \neq a_{i+1}\)). В начале концертного тура группа находится в городе \(a_1\).

Гарантируется, что группа может дать все концерты.

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

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

Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку „infinitely kind“.

Примеры
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
Выходные данные
6
5 6 5 7 2 3
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
Выходные данные
infinitely kind
#3559
Алгоритм Краскала
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Первая строка входных данных содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них разные, в пределах от 0 до N–1 каждое, и обозначают концы соответствующего ребра, третье — в пределах от 1 до 1000000000 и обозначает длину этого ребра. Гарантировано, что все ребра имеют различные длины. Количество вершин графа не превышает 80000, количество рёбер — 100000.

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

Выведите на стандартный выход (экран) либо единственное число — сумму длин рёбер остовного дерева минимального веса (если граф связный), либо единственную фразу «NON-CONNECTED» (без кавычек, через дефис) если граф не связный.

Примечание

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

Указания.

Алгоритму Краскала, в отличие от предыдущих графовых задач, совершенно не нужно, чтобы граф был представлен списками смежности. Зато нужно сортировать ребра по длине. Разрешается самому написать сортировки (со сложностью O(N logN), иначе программа окажется не достаточно эффективной). Но рекомендуется заставить работать стандартный алгоритм sort. Для него нужно подключить заголовочный файл algorithm и указать, каким образом сравнивать структуры, представляющие ребра. Для этого можно перегрузить (overload) операцию сравнения operator < для типа, представляющего ребро (подробнее см. в книгах, help-е, а также в указаниях к задаче «Алгоритм Дейкстры за M logN»).

Примеры
Входные данные
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
Выходные данные
19
#3586
Магнитные подушки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Город будущего застроен небоскребами, для передвижения между которыми и парковки транспорта многие тройки небоскребов соединены треугольной подушкой из однополярных магнитов. Каждая подушка соединяет ровно 3 небоскреба и вид сверху на нее представляет собой треугольник, с вершинами в небоскребах. Это позволяет беспрепятственно передвигаться между соответствующими небоскребами. Подушки можно делать на разных уровнях, поэтому один небоскреб может быть соединен различными подушками с парами других, причем два небоскреба могут соединять несколько подушек (как с разными третьими небоскребами, так и с одинаковым). Например, возможны две подушки на разных уровнях между небоскребами 1, 2 и 3, и, кроме того, магнитная подушка между 1, 2, 5.

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

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

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

В первой строке входного файла находятся числа N и M — количество небоскребов в городе и количество работающих магнитных подушек соответственно (3 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). В каждой из следующих M строк через пробел записаны три числа — номера небоскребов, соединенных подушкой. Небоскребы пронумерованы от 1 до N. Гарантируется, что имеющиеся воздушные подушки позволяют перемещаться от одного небоскреба до любого другого.

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

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

Примеры
Входные данные
3 1
1 2 3
Выходные данные
1
1
Входные данные
3 2
1 2 3
3 2 1
Выходные данные
0
Входные данные
5 4
1 2 3
2 4 3
1 2 4
3 5 1
Выходные данные
1
4
#3706
Immediate Delivery
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

Вася и Петя работают курьерами в фирме "Мгновенная доставка". Сегодня им надо доставить огромное количество посылок по всему городу.

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

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

Офис компании "Мгновенная доставка" расположен на перекрестке номер 1.

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

В первой строке заданы целые числа n (1 ≤ n ≤ 18) и m - количество пунктов и дорог.

Следующие m строк описывают дороги. Каждая дорога задается тремя целыми числами: номерами перекрестков xi и yi, которые она соединяет, (1 ≤ x i, yi ≤ n) и временем ti, которое нужно, чтобы по проехать по ней (1 ≤ ti ≤ 1000). Между каждой парой перекрестков не более чем одна дорога. Никакая дорога не соединяет перекресток с самим собой.

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

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

Примечание
В примере выводить нужно только одно число. Здесь приведён пример разбиения, но его выводить не нужно.
Примеры
Входные данные
6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10
Выходные данные
40
4 1 2 3 4 3
3 1 2 5 6
Страница: << 42 43 44 45 46 47 48 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест