В сказочном королевстве N городов. Некоторые пары городов соединены дорогами, причем одну и ту же пару городов могут соединять несколько дорог. За границами городов дороги не пересекаются. По каждой дороге можно ехать в любом направлении. Помогите королю определить, сколько еще дорог нужно построить в королевстве, чтобы Его Величество смог совершить путешествие по всем дорогам, не проезжая дважды по каждой из них. Конечно (см пример ниже), он желает посетить каждый город. Путешествие короля должна начинаться и заканчиваться в одном и том же городе.
Технические условия. Вы вводите с клавиатуры количество городов в королевстве N (1 <= N <= 100) и количество пар городов К (1 <= K <= 10000). Затем в К группах по 3 числа Вы вводите номера городов и количества дорог, которые соединяют города(все числа не превышают 100). Все числа разделены пробелом. Вы выводите на экран минимально возможное количество дорог.
Вопрос: как получилось 3?
По моему мнению, можно объехать все дороги, начиная, например, из города 1, которые соединяют города 1-4, построить дорогу, например, в 5, проехать в 6, вернуться в 5 и построить дорогу в 1. Таким образом построено 2, а не 3 дороги.
Если я ошибся, то в чем ошибка?
Здравствуйте, olimp_20, Вы писали:
Ввод>> 7 6 1 21 1 3 14 1 3 42 5 3 43 5 6 2 Вывод>> 3
_>Вопрос: как получилось 3? _>По моему мнению, можно объехать все дороги, начиная, например, из города 1, которые соединяют города 1-4, построить дорогу, например, в 5, проехать в 6, вернуться в 5 и построить дорогу в 1. Таким образом построено 2, а не 3 дороги. _>Если я ошибся, то в чем ошибка?
Если добавить две дороги, то действительно можно будет объехать все дороги — здесь ты прав.
Но в твое варианте король не сможет вернуться в тот же город, из которого выехал.
Чтобы сделать это придется построить еще одну дополнительную дорогу — третью.
Согласно теореме, доказанной Эйлером, в графе без одиночных вершин эйлеров цикл существует тогда и только тогда, когда граф связный и в нём отсутствуют вершины нечётной степени.
Здравствуйте, Буравчик, Вы писали:
Б>Это задача про Эйлеров цикл
Задачка кажется простой, но с подводными грабельками.
1) Разбиваем граф на связные подграфы (пусть их будет N).
2) Для каждого подграфа определяем количество нечётных вершин si. В принципе, больше о подграфе ничего знать не нужно, он выглядил как ежик с si иголками, торчащими наружу.
3) Пусть суммарное количество нечётных вершин равно S = sum si.
4) Понятно, что надо связать подграфы между собой — добавив N-1 рёбер. А также сократить нечётные вершины — добавив (S/2)-1 рёбер. Две оставшиеся вершины можем себе позволить.
Здравствуйте, Кодт, Вы писали:
K>Две оставшиеся вершины можем себе позволить.
Нет, там по условию нужно вернуться в тот же город.
К>Вопрос, как сэкономить, объединив N-1 и (S/2)-1?
Тут главное — объединить компоненты связности в цикл, добавив, N ребер. В тех компонентах, в которых вершин с нечетной степенью нет, придется добавить два ребра одной из вершин, в тех, в которых вершины с нечетной степенью есть — взять любые две из них. Остальные вершины с нечетной степенью связывать можно как угодно. Таким образом количество дорог, которые нужно будет добавить равно S/2 + F, где F — количество компонент связности без вершин нечетной степени.
Здравствуйте, _DAle_, Вы писали:
K>>Две оставшиеся вершины можем себе позволить. _DA>Нет, там по условию нужно вернуться в тот же город.
А, точно. Тогда всё несколько проще.
_DA>Тут главное — объединить компоненты связности в цикл, добавив, N ребер. В тех компонентах, в которых вершин с нечетной степенью нет, придется добавить два ребра одной из вершин, в тех, в которых вершины с нечетной степенью есть — взять любые две из них. Остальные вершины с нечетной степенью связывать можно как угодно. Таким образом количество дорог, которые нужно будет добавить равно S/2 + F, где F — количество компонент связности без вершин нечетной степени.
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, Кодт, Вы писали:
K>>Две оставшиеся вершины можем себе позволить. _DA>Нет, там по условию нужно вернуться в тот же город.
К>>Вопрос, как сэкономить, объединив N-1 и (S/2)-1?
_DA>Тут главное — объединить компоненты связности в цикл, добавив, N ребер. В тех компонентах, в которых вершин с нечетной степенью нет, придется добавить два ребра одной из вершин, в тех, в которых вершины с нечетной степенью есть — взять любые две из них. Остальные вершины с нечетной степенью связывать можно как угодно. Таким образом количество дорог, которые нужно будет добавить равно S/2 + F, где F — количество компонент связности без вершин нечетной степени.
компонента 3-1-2-4 связана с 5-6 двумя дорогами + 1 компонента 5-6 = 3 дороги, вроде бы так, но...
S = sum si
si — как вычисляется? Если исходить из примера к задаче: компонента связности 3-1-2-4 si=1? Если 1, тогда для S=0, F=1? что-то не так...
Здравствуйте, olimp_20, Вы писали:
_>компонента 3-1-2-4 связана с 5-6 двумя дорогами + 1 компонента 5-6 = 3 дороги, вроде бы так, но... _>S = sum si _>si — как вычисляется? Если исходить из примера к задаче: компонента связности 3-1-2-4 si=1? Если 1, тогда для S=0, F=1? что-то не так...
В примере 3 компоненты связности {1, 2, 3, 4}, {5, 6}, {7}. Вершин с нечетной степенью две: 1 и 3 (S = 2), компонент, в которых нет вершин с нечетной степенью — 2 (F = 2). Ответ: 3. Пример ребер — это {6, 7}, {7, 1}, {3, 6}.
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, olimp_20, Вы писали:
_>>компонента 3-1-2-4 связана с 5-6 двумя дорогами + 1 компонента 5-6 = 3 дороги, вроде бы так, но... _>>S = sum si _>>si — как вычисляется? Если исходить из примера к задаче: компонента связности 3-1-2-4 si=1? Если 1, тогда для S=0, F=1? что-то не так...
_DA>В примере 3 компоненты связности {1, 2, 3, 4}, {5, 6}, {7}. Вершин с нечетной степенью две: 1 и 3 (S = 2), компонент, в которых нет вершин с нечетной степенью — 2 (F = 2). Ответ: 3. Пример ребер — это {6, 7}, {7, 1}, {3, 6}.
Я, видимо, иначе понимаю понятие "степень вершины"... Согласен, что будет три компоненты и две последние не имеют нечетных вершин. Но первая компонента, если ее нарисовать, то получится ромб с диагональю 1-4, и только из вершины 4 будет исходить 3+3+5=11 ребер. То есть вершина №4 нечетная, остальные четные:
№1 — "1+1+3", №2 — "1+5", 3 — "1+3". Почему тогда №1 и №3 должны быть нечетными?
Здравствуйте, olimp_20, Вы писали:
_>Я, видимо, иначе понимаю понятие "степень вершины"... Согласен, что будет три компоненты и две последние не имеют нечетных вершин. Но первая компонента, если ее нарисовать, то получится ромб с диагональю 1-4, и только из вершины 4 будет исходить 3+3+5=11 ребер. То есть вершина №4 нечетная, остальные четные:
Ошибся с нумерацией, не третья вершина, а четвертая, да.
_>№1 — "1+1+3",
1+1+3 = 5
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, olimp_20, Вы писали:
_>>Я, видимо, иначе понимаю понятие "степень вершины"... Согласен, что будет три компоненты и две последние не имеют нечетных вершин. Но первая компонента, если ее нарисовать, то получится ромб с диагональю 1-4, и только из вершины 4 будет исходить 3+3+5=11 ребер. То есть вершина №4 нечетная, остальные четные: _DA>Ошибся с нумерацией, не третья вершина, а четвертая, да.
Спасибо
_>>№1 — "1+1+3", _DA>1+1+3 = 5
Упс, мне стыдно...
Перекуём баги на фичи!
