ACMP 615: различия между версиями
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=615 ACMP #615 — Новый год] == Похожие задачи == * Инте…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
== Похожие задачи == | == Похожие задачи == | ||
* [[Интернет-олимпиада 25.02.2006, усложнённый уровень, D]] | * [[Интернет-олимпиада 25.02.2006, усложнённый уровень, D]] | ||
== Комментарии == | |||
Решение #1 | |||
[http://cstheory.stackexchange.com/questions/14690/reducing-a-minimum-cost-edge-cover-problem-to-minimum-cost-weighted-bipartie-per cstheory.stackexchange.com — Reducing a minimum cost edge-cover problem to minimum cost weighted bipartite perfect matching] | |||
Пусть minCost[i] — минимальная стоимость ребра, инцидентного вершине i. Заменим стоимости всех рёбер e.cost на e.cost - minCost[e.a] - minCost[e.b]. | |||
Найдём паросочетание минимальной стоимости в полученном графе, пусть его стоимость — pCost. Тогда ответ имеет стоимость (Σ(minCost[i]) + pCost), в ответ входят все рёбра паросочетания и минимальные рёбра, инцидентные вершинам, не насыщенным паросочетанием. | |||
Решение #2 | |||
Пусть d[i] — степень вершины i. Проведём рёбра пропускной способности (d[i] - 1) от истока к вершинам левой доли и от вершин правой доли к стоку. Стоимости всех рёбер исходного графа заменим на противоположные. | |||
Найдём поток минимальной стоимости в полученной сети, пусть его стоимость — fCost. Тогда ответ имеет стоимость (Σ(e.cost) + fCost), в ответ входят все рёбра исходного графа, не насыщенные потоком. | |||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Поток минимальной стоимости]] | [[Category: Задачи: Поток минимальной стоимости]] | ||
Текущая версия от 16:40, 7 августа 2016
Ссылка на задачу
Похожие задачи
Комментарии
Решение #1
Пусть minCost[i] — минимальная стоимость ребра, инцидентного вершине i. Заменим стоимости всех рёбер e.cost на e.cost - minCost[e.a] - minCost[e.b].
Найдём паросочетание минимальной стоимости в полученном графе, пусть его стоимость — pCost. Тогда ответ имеет стоимость (Σ(minCost[i]) + pCost), в ответ входят все рёбра паросочетания и минимальные рёбра, инцидентные вершинам, не насыщенным паросочетанием.
Решение #2
Пусть d[i] — степень вершины i. Проведём рёбра пропускной способности (d[i] - 1) от истока к вершинам левой доли и от вершин правой доли к стоку. Стоимости всех рёбер исходного графа заменим на противоположные.
Найдём поток минимальной стоимости в полученной сети, пусть его стоимость — fCost. Тогда ответ имеет стоимость (Σ(e.cost) + fCost), в ответ входят все рёбра исходного графа, не насыщенные потоком.