Нахождение количества компонент связности Для решения можно применить алгоритм обхода в глубину. Принцип простой — обходим рекурсивно все вершины, помечая их как посещенные. Как только обошли все, переходим к первой же, которую еще не посетили, если таковая существует, одновременно увеличивая на единицу число компонент связности. И так до тех пор, пока не кончатся все вершины. Описание алгоритма и пример: Нахождение мостов Алгоритм нахождения мостов основывается на поиске «циклов» — альтернативных путей между вершинами. Если такого пути не обнаруживается, то ребро является мостом. Описание алгоритма и пример: Этот алгоритм можно модифицировать, чтобы находить число вершин с разных сторон от моста. Попыток сдать задачу «Перестройка» было 621, из которых 137 – успешных (22%). (pastebin)
подсчет количества вершин с каждой стороны от моста.
нахождение мостов;
подсчет количества компонент связности;
Эта задача предполагает некоторые знания из области теории графов. Вершинами у нашего графа являются города, ребрами — дороги. В теории графов есть понятие связности графа — наличия пути из любой вершины в любую. В данном случае изначально мы имеем граф неизвестной связности, а в итоге должны получить граф обязательно связный. Есть понятие компоненты связности графа — это максимальное по включению множество связанных между собой вершин. Соответственно число компонент связности — это количество несвязанных между собой групп вершин. Например, в случае, если ребер графа (=дорог) нет вообще, число компонент связности равна количеству вершин (=городов). Также введем понятие «моста» — ребра, удаление которого делает граф несвязным, то есть делит его на несвязанные части. Итак, вспомним суть реформы из постановки задачи: одно существующее ребро (=дорога) удаляется, и добавляется другое в место, где его раньше ребра не было. Нужно посчитать число вариантов такой реформы. Также по условиям задачи помним, что наша реформа должна приводить к связному графу, т.е. с одной компонентой связности. Изначально количество групп несвязных между собой городов-вершин может быть любым. Очевидно, что при числе компонент связности более двух сделать в итоге связный граф добавлением одного ребра у нас никак не получится, ведь так мы свяжем только две группы между собой, а их — больше. Вот иллюстрация этого варианта: Следовательно, в этом простейшем случае ответ — ноль вариантов. В случае, если мы имеем дело с двумя группами, то есть компонент связности две, то количество вариантов рассчитывается следующим образом. Сначала нужно найти, какие ребра являются «мостами» — ведь при удалении этих ребер мы приводим все к первому, рассмотренному выше варианту. Добавить их же назад мы не можем, так как по условиям задачи добавить можно только там, где ребер не было. Поскольку в итоге мы должны получить связный граф, добавленное ребро должно соединять вершины из разных компонент связности — делать из несвязного графа связный. Две группы из N и M вершин можно связать между собой NxM способами. Следовательно, число реформ у нас получится NxMxC, где C = число ребер без учета тех из них, что являются мостами. Третий случай, когда мы имеем изначально связный граф — самый сложный. В этом случае компонента связности одна, но некоторые ребра могут являться мостами. В итоге число вариантов реформ является суммой двух слагаемых: первое — число вариантов удаления ребер-не-мостов, второе – число вариантов удаления ребер-мостов. Общее количество ребер можно посчитать по числу вершин: n * (n-1))/2 (где n = число вершин). Количество ребер, которые можно добавить, вычисляется вычитанием из общего количества числа имеющихся ребер. Так мы получаем первое слагаемое — число ребер, не являющихся мостами, помноженное на число ребер, которые можно добавить. При удалении «моста» мы должны соединить ребром две получившиеся компоненты связности, развязанные группы вершин. Количество способов это сделать равно произведению вершин справа от моста на количество вершин слева от моста, уменьшенное на единицу, так как сам мост обратно мы поставить не можем по условию задачи. В итоге для решения этой задачи необходимо знание следующих алгоритмов из теории графов:
По условиям задачи существовало множество дорог между городами. Между любыми двумя городами проложено не более одной дороги. В результате некой дорожной реформы одна из существующих дорог должна была быть разрушена, а другая, из не проложенных ранее, должна была быть построена, причем таким образом, чтобы в итоге из любого города в любой можно было доехать (изначально это могло быть не так). Также есть уточнение, что дорога не может вести из города в него же. Необходимо было посчитать количество вариантов реализации этой реформы.
Вторая задача была посложнее.
«Перестройка»
Попыток сдать задачу «Параллелепипед» было 1479, из которых 639 – успешных (43%). Эта задача оказалась наиболее доступной – число попыток более чем в два раза больше, чем на других задачах, высокий процент успешности.
cout << ((ans) ? "yes" : "no") << endl;
for (int j = 0; j < 12; j++)
for (int i = 0; i < 12; i++)
for (int i = 0; i < 12; i++)
for (int i = 0; i < 12; i++)
#include <cstdio>
#include <iostream>
Задача «Параллелепипед» заключалась в том, чтобы по известным длинам двенадцати спичек проверить, можно ли из них склеить каркас параллелепипеда. Эта задача была самой простой и с нее начали решение все участники. Тут следовало вспомнить, что параллелепипед — это фигура, основанием которой служит параллелограмм — четырехугольник, у которого стороны попарно параллельны. У параллелепипеда есть три размерности в 12 ребрах — длина, ширина и высота. Следовательно, необходимо ответить на вопрос, есть ли среди входных данных ровно три группы по четыре одинаковых числа. Чтобы понять это, необходимо отсортировать все числа и убедиться, что получилось три группы по четыре одинаковых числа (одинаковых по крайней мере внутри каждой группы). Если это так, выводить yes, иначе — no.
«Параллелепипед»
Первый квалификационный раунд
Russian Code Cup — Раунд
Комментариев нет:
Отправить комментарий