ACMP 615

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

• ACMP #615 — Новый год

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

• Интернет-олимпиада 25.02.2006, усложнённый уровень, D

Комментарии

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