--->
12 задач
<---
Источники
Дан неориентированный граф без кратных ребер и петель. В нем уже содержится некоторое (возможно, нулевое) количество ребер. Можно за определенную плату добавлять в него новые ребра (плата своя для каждого ребра). Требуется за наименьшую плату сделать граф связным.
В первой строке входных данных содержится одно целое число \(N\) (1 ≤ \(N\) ≤ 50) – количество вершин в исходном графе. Далее в \(N\) строках записано по \(N\) неотрицательных целых чисел в каждой ( \(j\) -е число в \(i\) -й строке соответствует стоимости добавления ребра, соединяющего вершины \(i\) и \(j\) , 0 соответствует уже существующему ребру, положительное число – несуществующему), числа не превышают 100. Матрица симметрична.
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.
3 0 0 5 0 0 0 5 0 0
0
|
Максимальное время работы на одном тесте: |
4 секунды |
|
Максимальный объем используемой памяти: |
64 мегабайта |
Алексей работает системным администратором в локальной домовой сети. Его сеть соединяет множество квартир и располагается в нескольких зданиях.
Сеть постоянно расширяется и Алексею поручено проложить новый участок сети. У него есть схема, на которой указаны все возможные соединения между парами квартир и для каждого соединения он знает длину провода, необходимого для его прокладки. Его цель состоит в том, чтобы все квартиры были подключены к сети (возможно через другие квартиры).
Компания, в которой работает Алексей покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене 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.
Пример
|
Входные данные |
Выходные данные |
|
6 7 1 2 7 2 6 5 1 4 8 2 3 5 3 4 5 5 6 6 3 5 3 2 11 3 100 |
65 1 5 2 6 4 6 5 6 7 5 |
С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии “Майбуття” к одной из школ города (к какой неважно), а также соединить линиямии электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником “Майбуття”, либо с одной из тех школ, которые имеют надежное электроснабжение.
Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).
Напишите программу, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.
В первой строке входного файла находятся два натуральных числа, разделенных пробелом: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 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.
Гарантируется, что для входных данных существует две различные схемы надёжного электроснабжения.
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 и m - количество вершин и ребер графа соответственно (1≤n≤20000, 0≤m≤100000). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi - номера концов ребра и его вес соответственно (1≤bi,ei≤n, 0≤wi≤100000).
Граф является связным.
Выведите единственное целое число - вес минимального остовного дерева.
4 4 1 2 1 2 3 2 3 4 5 4 1 4
7
На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих Ki (3 ≤ Ki ≤ 30, 1 ≤ i ≤ N) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:
Oтрезок соединяет только пару супермногоугольников.
Суммарная длина отрезков была минимальна.
Между любыми двумя супермногоугольниками должен существовать путь (последовательность некоторых отрезков и частей границ супермногоугольников).
Формат входных данных
В первой строке число N. В следующих N строках. Число Ki и Ki пар чисел – координаты вершин.
Формат выходных данных
В первой строке число М и сумма длин найденных отрезков с точностью 10-3. В следующих М строках числа L1 X1 Y1 L2 X2 Y2 – номера супермногоугольников и координаты концов отрезков с точностью 10-3.
Примеры
| Входные данные | Выходные данные |
| 2 3 1 0 2 0 1 1 4 6 5 7 5 7 6 6 6 | 1 6.364 1 1.500 0.500 2 6.000 5.000 |
| 3 3 0 0 1 0 0 1 4 5 5 6 5 6 6 5 6 3 0 5 1 6 0 6 | 2 8.000 3 1.000 6.000 2 5.000 6.000 1 0.000 1.000 3 0.000 5.000 |