e-olymp 7254. Отрезки

Задача

Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть [latex]N[/latex] прямых отрезков.

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

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

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

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

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

Тесты

Входные данные Выходные данные
1 4
1 1
2 2
3 3
4 4
9

Код

 

 

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

e-olymp 7233. Путешествия в космосе

Задача

Инфраструктура космической галактики состоит из [latex]N[/latex] планет и [latex]M[/latex] прямых межпланетных маршрутов, каждый из которых связывает ровно две разные планеты. Расстояния в космосе достаточно большие, поэтому, если планеты не имеют прямого сообщения, то во время перелетов используют транзитные планеты.

Популярностью планеты [latex]k[/latex] будем считать количество пар различных планет [latex]i[/latex] и [latex]j[/latex], перелет между которыми возможен только при использовании планеты [latex]k[/latex] [latex] (i, j, k = 1..N)[/latex]. Для заданной системы космических сообщений найти значение максимальной популярности и количество планет, достигающих её.

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

В первой строке натуральные числа [latex]N[/latex] и [latex]M[/latex] ([latex]1 \leqslant N \leqslant 1000[/latex], [latex]1 \leqslant M \leqslant 5000[/latex]). В следующих [latex]M[/latex] строках по два натуральных числа, описывающие маршрут между планетами [latex]i[/latex] и [latex]j[/latex] [latex](i, j, k = 1..N)[/latex].

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

Ответ к задаче.

Тесты

Входные данные Выходные данные Схема
1 4 4
1 2
1 3
1 4
2 3
5 1
2 14 14
1 2
2 3
2 4
3 5
1 6
6 7
7 8
8 6
1 9
9 10
10 11
9 12
1 13
13 14
75 1
3 4 4
1 2
2 3
3 4
4 1
3 4

Код

 

 

Решение

Для начала представим полученный граф из планет в виде списка смежности (список, где каждой вершине соответствует список смежных ей других вершин). Так как нам надо получить значение наибольшей популярности, будем поочередно убирать (по сути заранее отмечать ее как посещенную) каждую из вершин и смотреть, между сколькими парами вершин нельзя составить маршрут. Для этого воспользуемся depth-first search. Его суть состоит в том, что мы берем любую вершину и начинаем рекурсивно проходить по всем ее соседям, а потом по их соседям и так далее. Каждую посещенную вершину мы отмечаем, чтобы при попадании на посещенную ранее вершину выйти из рекурсии. Таким образом, мы запускаем рекурсивную функцию пока остаются не посещенные вершины. В конце мы получим список связных подграфов и количество вершин в каждом из них. Чтобы получить популярность искомой вершины, мы суммируем кол-во остальных вершин (так как у них нет маршрута к убранной вершине) и поочередное произведение кол-ва вершин полученных подграфов.

Ссылки