ACMP 615

Материал из Олимпиадное программирование в УлГТУ
Версия от 16:40, 7 августа 2016; Ctrlalt (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Ссылка на задачу

Похожие задачи

Комментарии

Решение #1

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), в ответ входят все рёбра исходного графа, не насыщенные потоком.