|
Название задачи: Домино . |
 |
Условие
Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до M включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).
Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.
Некоторые костяшки были удалены из полного набора. Требуется определить, какое минимальное количество цепочек нужно выложить из оставшихся в наборе костяшек, чтобы каждая из них принадлежала ровно одной цепочке.
Задание
Напишите программу
DOMINO, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.Входные данные
В первой строке входного файла
DOMINO.DAT содержится одно целое число M (0≤M?100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число N, равное количеству костяшек, удаленных из полного набора. Каждая i-я из последующих N строк содержит по два числа Ai и Bi. Это количества точек на половинках i-й удалённой костяшки.Выходные данные
Единственная строка выходного файла
DOMINO.SOL должна содержать одно целое число L - минимальное количество цепочек.Пример входных и выходных данных
|
DOMINO.DAT |
DOMINO.SOL |
|
7 2 7 5 3 4 |
2 |
Также доступны документы в формате DOC
Решение
Решения членов жюри Всеукраинской олимпиадыТесты
· Представим себе неориентированный граф с (M+1) вершинами, помеченными числами от 0 до M. Ребра этого графа соответствуют костяшкам домино.
· Очевидно, что ребра из разных компонент связности не могут находиться в одной цепочке, поэтому для начала разделим граф на компоненты связности. Также из графа следует удалить компоненты, не содержащие ребер (отдельные вершины).
· В каждой компоненте связности считаем K - количество вершин с нечетной степенью (нечетных вершин). Минимальное количество цепочек в этой компоненте равняется 1, если K=0, и K/2, если K>0. Суммарное количество цепочек равняется сумме K по всем компонентам связности.
Доказательство
· Эйлер доказал, что, если в связном неориентированном графе все вершины имеют четные степени, то, начав из любой вершины, можно обойти все ребра и вернуться в исходную вершину, т.е. построить Эйлеров цикл.
· Представим себе связный неориентированный граф с K нечетными вершинами, K>0. Докажем, что этот граф можно разложить на K/2 цепей, так что каждое ребро графа будет принадлежать ровно одной.
· Начнем строить одну цепь с любой нечетной вершины, проходя по любым еще не пройденным ребрам. Очевидно, что эта цепь закончится в другой нечетной вершине. Запомним эту цепь и удалим ее ребра из графа. При этом количество нечетных вершин уменьшится на 2 - это начальная и конечная вершины полученной цепи.
· Если после удаления цепи граф разделился на несколько компонент связности, то в каждой компоненте осталось четное количество нечетных вершин.
· Аналогичным образом строим и удаляем цепи, пока не закончатся нечетные вершины. Всего цепей - K/2. После этого оставшийся граф состоит из нескольких компонент связности, и в нем отсутствуют нечетные вершины.
· Далее среди запомненных находим любую цепочку, содержащую вершину, у которой остались инцидентные ребра в оставшемся графе. Согласно Эйлеру, начиная с этой вершины и заканчивая в ней, можно обойти все ребра соответствующей ей компоненты связности оставшегося графа. Поэтому вставляем эту компоненту целиком в найденную цепочку на место рассматриваемой вершины и удаляем ее из графа.
· Действуем аналогичным образом, пока можем найти такую цепочку. Если цепочка не найдена, а в графе еще остались ребра, значит, исходный граф был несвязным, что противоречит условию.
· Если ребер в графе не осталось, то цепочек, удовлетворяющих указанному условию больше нет. Итог: цепочек K/2, каждое ребро исходного графа входит ровно в одну цепочку, ЧИТД.
Также доступны документы в формате DOC
