Решаю задачу покрытия доминошками клетчатой фигуры (произвольной формы). Для этого пытаюсь применить поиск максимального потока: каждую клетку соединяем ребром с соседними (от 0 до 4), добавляем исток (из него рёбра веса 1 в каждую чёрную клетку), и исток (В него ИЗ каждой белой клетки рёбра веса 1). От чёрной клетки к белым соседям (если есть) рёбра имеют вес 1, обратные веса 0. Любой поток сквозь такой граф соответствует укладке доминошин на фигуре, максимальный поток — максимальная укладка.
Для поиска максимального потока использую алгоритм Форда-Фалкерсона с выбором кратчайшего пути. Задача не проходит по времени (реализация графа через списки смежности, через матрицу пробовал — не прошла по памяти). Есть ли более быстрые алгоритмы для решения этой задачи ? Или просто я криво реализовал Форда-Фалкерсона ? Код могу дать, он загружен в файле у меня в профиле, как присоединить файл к сообщению — не знаю. Использую язык C/C++ (от C++ только выделение динамической памяти).
Здравствуйте, almaz0, Вы писали:
A>Есть ли более быстрые алгоритмы для решения этой задачи ?
Поиск максимального паросочетания в двудольном графе же. Поиск максимального потока — более общая задача.
A>Мне казалось, алгоритм Куна (для поиска максимального паросочетания) работает по веремени также, как и Форд-Фалкерсон. Или это не так ?
Но для поиска максимального паросочетания есть алгоритмы и побыстрее.
