|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 11 Mar 2002 21:47:14
To : All
Subject : Или я сильно туплю или одно из двух...
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый All! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Имеем: задачу о паросочетаниях.
Алгоритм:
1. Жадно берем первое попавшееся паросочетание
2. "Раскрашиваем" ребра (насыщенные имеют одну направленность, ненасыщенные -
другую)
3. Ищем, в теперь уже ориентированном, графе путь который начинается ненасыченым
ребром и заканчивается ненасыщенным ребром и "перекрашиваем" (меняем в каждом
ребре пути направленность на противоположную)
4. Повторяем п.3, пока можем.
5. Выводим результат.
Пишем, компилим - не пашет...
ГДЕ БАГА??????????
ЗЫ:Каждый пункт проверен четко, т.ч. реализация отвечает написанному здесь -
100%.
Good bye, mister All _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Все в Голом Деде пишут послания, Winamp поставлен на паузу... (с)~Сплин
--- А у твоего ГолДеда стоит... фильтрация мессаг???
* Origin: Телепузик спать ложится - программист за комп садится. (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
