Задачи, сводящиеся к алгоритму Форда-Фалкерсона

↑

⇐ ПредыдущаяСтр 19 из 28Следующая ⇒

Задача о максимальном потоке является классической и имеет множество применений. Напомню постановку проблемы. Дан взвешенный ориентированный граф с неотрицательными пропускными способностями. Выделены две вершины: исток S и сток T такие, что любая другая вершина лежит на пути из S в T. Потоком назовем функцию F: V x V с такими свойствами

1. Ограничение пропускной способности. Поток по ребру не может быть больше его (ребра) пропускной способности.

2. Антисимметричность. Для каждого ребра (u, v): F(u, v) = -F(v, u).

3. Сохранение потока. Для каждой вершины (кроме S и T), количество входящего потока (отрицательного) равен количеству исходящего потока (положительного).

Задача о максимальном паросочетании. На вход дается N — количество мальчиков, M — количество девочек и список, какой мальчик с какой из девочек хочет танцевать (таких может быть несколько). Надо определить максимальное количество одновременно танцующих пар.

Испорченный паркет. У паркета NxM, некоторые клетки могут быть испорчены. Их необходимо закрыть новыми плитками. Плитки бывают размером 2х1 (можно поворачивать, но нельзя разрезать) ценой А, и 1х1 ценой B. Спрашивается, какую минимальную сумму нужно потратить, что бы заложить испорченные плитки паркета. Естественно, новые плитки не должны перекрывать никакие другие плитки.

Задача живопись. Дана матрица N*M с клетками, покрашенными либо в черный, либо в белый цвета. W — цена перекраски черного квадрата в белый, B — белого в черный. После перекраски, между всеми соседними квадратами разных цветов нужно провести серую линию, ценой G. Надо так отпимально перекрасить матрицу (или ничего не делать), что бы потратить минимальную сумму.

Минимальный разрез. Дан граф. Сколько вершин надо удалить, что бы не существовало пути из A в B?И т.д.

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте