| Условие задачи | | Прогресс |
|
Темы:
Минимальный каркас
Алгоритмы на графах
С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии “Майбуття” к одной из школ города (к какой неважно), а также соединить линиями электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником “Майбуття”, либо с одной из тех школ, которые имеют надежное электроснабжение.
Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).
Напишите программу, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.
Входные данные
В первой строке входного файла находятся два натуральных числа, разделенных пробелом: N (3 <= N <= 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1 <= Ci <= 300) от школы Ai до школы Bi (i=1,2,…,N).
Выходные данные
В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом – две наименьшие стоимости схем (S1 <= S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.
Гарантируется, что для входных данных существует две различные схемы надёжного электроснабжения.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121 |
| |
![]()
|
|
Темы:
Система непересекающихся множеств
Древовидные структуры данных
Минимальный каркас
Беси расположена на сети из N (2≤N≤105) вершин помеченных 1…N и 2N порталов помеченных 1…2N. Каждый портал соединяет две различных вершины u и v (u≠v). Множество порталов может соединять некоторую пару вершин.
Каждая вершина v соседняя для четырёх различных порталов. Список порталов вершины v задаётся как pv=[pv,1,pv,2,pv,3,pv,4].
Ваше текущее положение может быть представлено упорядоченной парой (current vertex,current portal); то есть парой (v,pv,i) где 1≤v≤N и 1≤i≤4. Вы можете использовать одну из следующих операций для изменения своего текущего положения:
Изменить текущую вершину перемещением через текущий портал.
Переключить текущий портал. В каждой вершине первые два портала в списке объединены в пару и последние два портала в списке также объединены в пару. Поэтому если Ваше текущее состояние (v,pv,2), то Вы можете переключиться чтобы использовать портал (v,pv,1) и обратно. Аналогично, если Ваше текущее положение (v,pv,3) Вы можете переключиться на портал (v,pv,4) и обратно. никакие другие переключения не разрешены (например, Вы не можете переключиться с портала pv,2 на портал) pv,4).
Всего имеется 4N различных состояний. К несчастью, может не оказаться, что что любое состояние достижимо из любого с помощью последовательности заданных операций. Поэтому, за цену cv (1≤cv≤1000) мунов вы можете сделать перестановку списка порталов соседних вершине v, в любом желаемом Вами порядке. После этого первые два портала в списке объединяются в одну пару, а последние два портала - в другую пару.
Например, если Вы переставить порталы вершины v в порядке [pv,3,pv,1,pv,2,pv,4], Это означает. что если Вы в вершине v,
Если Вы в портале pv,1, Вы можете переключиться на портал pv,3 и обратно
Если Вы в портале pv,2, Вы можете переключиться на портал pv,4 и обратно
Теперь Вы не можете переключаться с портала pv,1 на pv,2, или с портала pv,3 на портал pv,4 и обратно.
Вычислите минимальное количество мунов, требуемых для модификации сети таким образом, чтобы сделать достижимым каждое состояние из каждого состояния. Гарантируется, что тестовые данные сконструированы таким образом, что существует хотя бы один способ такой модификации сети.
Входные данные:
Первая строка содержит N.
Каждая из следующих N строк описывает вершину. Строка v+1 содержит 5 разделённых одиночными пробелами целых чисел cv,pv,1,pv,2,pv,3,pv,4.
Гарантируется, что для каждой v все pv,1,pv,2,pv,3,pv,4 различны, и каждый портал появляется в списках ровно двух вершин.
Выходные данные:
Одна строка содержит минимальное количество мунов требуемых для модификации сети чтобы сделать возможным достижимость каждого состояния из другого состояния.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5 |
13 |
Достаточно сделать перестановку списков вершин 1 и 4. Это требует c1+c4=13 мунов. Перестановки такие: p1=[1,9,4,8] и p4=[7,4,6,3]. |
| |
![]()
|
|
Темы:
Минимальный каркас
Структуры данных
Дерево отрезков, RSQ, RMQ
Обход в глубину
Алгоритмы на графах
Фермер Джон обнаружил, что разные типы коров любят разные типы травы. Однако он должен правильно их высаживать, чтобы не навредить.
Ферма Джона состоит из NN (1≤N≤200,000), полей, и MM пар полей соединены двунаправленными дорожками (1≤M≤200,000). Используя эти дорожки, можно пройти от любого поля к любому другому полю. Каждая дорожка имеет целочисленную длину в интервале 1…1,000,000. Любая пара полей соединена не более чем одной прямой дорожкой.
В каждом поле ФД изначально посадил один из KK типов травы (1≤K≤N). Через некоторое время, однако, он может решить изменить тип травы на некоторых из полей. Он называет это операцией "обновления".
После каждого обновления, ФД хочет знать длину кратчайшего пути между двумя полями, имеющими различные типы травы. То есть, среди всех пар полей, имеющих различные типы травы, он хочет узнать, какие два поля ближайшие друг к другу. Гарантируется, что всегда имеется как минимум одна пара полей с различными типами травы.
В 30 процентах тестов каждое поле непосредственно соединено не более чем с 10 дорожками.
ФОРМАТ ВВОДА:
Первая строка ввода содержит четыре целых числа N, M, K, Q, где Q - количество операций обновления (1≤Q≤200,000). Следующие M строк описывают дорожки. Каждая строка содержит три целых числа A, B, L, указывающих, что есть дорожка между полями A, B и её длина L. (A, B - целые числа в интервале 1…N). Следующая строка указывает начальный тип травы для каждого поля (N целых чисел в интервале 1…K). Затем идут Q строк, каждая из которых описывает одну операцию обновления двумя целыми числами A и B, означающими, что на поле A типе травы изменён на B.
ФОРМАТ ВЫВОДА:
Для каждой операции обновления выведите длину кратчайшего пути между двумя полями с различными типами травы, после применения этой операции обновления.
| Ввод |
Вывод |
|
3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2
|
1
3
3
1
|
| |
![]()
|
|
Темы:
Минимальный каркас
Дан неориентированный граф без кратных ребер и петель. В нем уже содержится некоторое (возможно, нулевое) количество ребер. Можно за определенную плату добавлять в него новые ребра (плата своя для каждого ребра). Требуется за наименьшую плату сделать граф связным.
Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N положительных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j ), числа не превышают 100. В следующих N строках записаны по N чисел, каждое из которых является единицей или нулем (1, если вершины соединены, и 0, если не соединены). Обе матрицы симметричны.
Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.
| |
![]()
|
|
Темы:
Минимальный каркас
Даны несколько точек на плоскости, некоторые из которых соединены отрезками. Множество точек называется связанным, если из любой его точки можно перейти в любую точку, перемещаясь только по отрезкам (переходить с отрезка на отрезок возможно только в точках исходного множества). Можно за определенную плату добавлять новые отрезки (стоимость добавления равна длине добавляемого отрезка). Требуется за минимальную стоимость сделать данное множество связанным.
Входные данные
В первой строке входных данных содержится одно целое число N
(1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.
Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения с точностью 5 знаков после запятой.
| |
![]()
|
|
Темы:
Минимальный каркас
Дан неориентированный граф без кратных ребер и петель. В нем уже содержится некоторое (возможно, нулевое) количество ребер. Можно за определенную плату добавлять в него новые ребра (плата своя для каждого ребра). Требуется за наименьшую плату сделать граф связным.
Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N неотрицательных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j, 0 соответствует уже существующему ребру, положительное число – несуществующему), числа не превышают 100. Матрица симметрична.
Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.
| |
![]()
|
|
Темы:
Минимальный каркас
Задача о рюкзаке
Алексей работает системным администратором в локальной домовой сети. Его сеть соединяет множество квартир и располагается в нескольких зданиях.
Сеть постоянно расширяется и Алексею поручено проложить новый участок сети. У него есть схема, на которой указаны все возможные соединения между парами квартир и для каждого соединения он знает длину провода, необходимого для его прокладки. Его цель состоит в том, чтобы все квартиры были подключены к сети (возможно через другие квартиры).
Компания, в которой работает Алексей покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене P5 и P6 рублей за метр. При этом в наличии имеется только Q5 метров кабеля пятой категории и Q6 метров кабеля шестой категории.
Алексею необходимо составить план постройки сети с наименьшими затратами. План представляет собой список соединений между квартирами, при этом каждому соединению должно быть приписано, кабель какой категории будет проложен между этими квартирами (пятой или шестой). Стоимость прокладки этой сети равна сумме стоимости прокладки всех соединений. Общая длина кабеля каждой категории не должна превышать количество кабеля, имеющегося в магазине.
Входные данные
В первой строке входного файла содержится число N — количество квартир, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10 000).
Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.
Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10 000) .
Выходные данные
Если все квартиры можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N-1 строк должны содержать описание соединений, представленных двумя числами каждое: Ai и Ci, где Ai — номер соединения в списке возможных соединений (от 1 до M), а Ci задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.
Если все квартиры соединить невозможно выведите слово Impossible.
| |
![]()
|