|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 12 Mar 2002 06:34:32
To : Alexander Shmidt
Subject : Re: Или я сильно туплю или одно из двух...
--------------------------------------------------------------------------------
До меня дошли слухи, что *11.03.02* *20:47:14* пролетало сообщение
от Alexander к *All* про *"Или я сильно туплю или одно из двух..."*. И я решил
вмешаться.
AS> Алгоритм: 1. Жадно берем первое попавшееся паросочетание 2.
AS> "Раскрашиваем" ребра (насыщенные имеют одну направленность, ненасыщенные
AS> - другую) 3. Ищем, в теперь уже ориентированном, графе путь который
AS> начинается ненасыченым ребром и заканчивается ненасыщенным ребром и
AS> "перекрашиваем" (меняем в каждом ребре пути направленность на
AS> противоположную) 4. Повторяем п.3, пока можем. 5. Выводим результат.
AS> Пишем, компилим - не пашет...
AS> ГДЕ БАГА??????????
В пукте 3 должна быть добавочка, что он закнчивается на непоюзанную вершину,
и соседние ребра в пути раскрашены по разному.
А вообще имхо лучше сделать так:
Добавляем вершины по очереди. Действуя как бы по индукции. Т.е. после i-го
шага у нас построено макс паросочетание для первых i вершин. Hа i+1 шаге
добавляем новую вершины, и ищем в графе путь начинающийся в этой вершине,
который идет то по поюзанному, то по непоюзанному ребру, и заканчивается
непоюзанной вершиной. Если пусть есть то перекрашиваем все ребра пути.
ps. А у тебя вообще граф двудольный, или как? А то не в двудольном графе
при реализации есть опасное место где можно наглючить.
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Металл сила - всем рэперам могила. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Или я сильно туплю или одно из двух... 