Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Feedback » Max Matching - Edmonds
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
>Единственная тонкость — при проверке, что эту вершину мы ещё не посещали, надо смотреть не в массив used, а в массив p — именно он заполняется для посещённых нечётных вершин. Если мы в вершину ещё не заходили, и она оказалась ненасыщенной, то мы нашли увеличивающую цепь, заканчивающуюся на вершине , возвращаем её.
Можно пояснить, почему нельзя использовать used?
>Единственная тонкость — при проверке, что эту вершину мы ещё не посещали, надо смотреть не в массив used, а в массив p — именно он заполняется для посещённых нечётных вершин. Если мы в вершину ещё не заходили, и она оказалась ненасыщенной, то мы нашли увеличивающую цепь, заканчивающуюся на вершине , возвращаем её.
Можно пояснить, почему нельзя использовать used?
У меня есть предположение, что поиск может придти в вершину цветка - в таком случае вершина будет помечена как used, но previous будет равно -1. В таком случае возможно увеличение пути (аугментация), используя часть пути цветка.
Да-да, но кажется, что аналогичная ситуация может быть не только с корнем цветка, а с любой четной его вершиной.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Feedback » Max Matching - Edmonds