ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98849
Темы:    [ Обход графа в ширину ]
[ Прочие задачи на сообразительность ]
Сложность: 3+
Классы:
Название задачи: Домино .
В корзину
Прислать комментарий

Условие

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 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

Источники и прецеденты использования

олимпиада
предмет информатика
Название Всеукраинская олимпиада по информатике
год
Год 2005
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .