Comments 1
Остается только доказать правильность этого метода, и это несложно — подумайте сами.
Как обычно бывает со многими "это очевидно" - автор не смог сам доказать.
Такое объяснение может дать интуицию того, что именно алгоритм делает. Может даже помогает его запомнить. Но без теорем, лемм, математической индукции и всей этой "скучной" мишуры вы не докажете, что алгоритм работает.
Почему вот тут, если одна девочка попробовала все "ребра", не нашла себе пару, к ней не надо больше никогда возвращатся? Ведь подобавляв других девочек мы что-то поменяем в рассадке, почему не может вдруг оказаться так, что вот та девочка без пары теперь сможет найти себе пару? Если это не так, то алгоритм был бы за O(N^2M), ведь после каждой перерассадки надо было бы опять проходится по всем девочкам без пары и запускать поиск.
Почему вы в dfs не зачищаете пометки после поиска от каждого ребра? Вот попросила девочка 3 мальчика 1 с ней сесть, он спросил девочку 1, та спросила мальчика 2, потом что-то и еще и не нашлось ничего. Почему вот тут девочка 1 даже не будет справшить мальчика 2 с ней сесть? Ведь теперь мальчик 1 не пытается с ней сесть, девочка 3 никуда от него не ушла, почему не надо запускать всю цепную реакцию опять?
Почему алгоритм вообще находит максимальное паросочетание? Почему обязательно найдется такая цепочка из девочек-мальчиков, увеличивающая количество пар, если паросочетание не максимально?
Еще, этот алгоритм - это алгоритм Куна, а не "венгерский". "Венгерским" называют другой алгоритм для поиска паросочетания минимальной стоимости ну или для решения задачи о назначениях.
Такой процесс называют построением максимального потока.
Вообще нет. Абсолютно нет, как вы вдруг переключились на потоки? Это называется построение удлинняющей цепочки.
Если там вся книга такая, то могу лишь посоветовать никому ни при каких обстоятельствах к ней не приближатся вообще.
Американские горки — поиск наибольшего паросочетания в двудольном графе