Project selection / задача о выборе проектов — как свести максимизацию прибыли к минимальному разрезу?
Классическая задача: есть проекты с прибылью (или убытком) и зависимости «чтобы взять проект A, надо взять проект B». Нужно выбрать подмножество проектов с максимальной суммарной прибылью при соблюдении зависимостей. Слышал, что это решается через минимальный разрез / max-flow. Как построить сеть?
2 ответа
Это каноническая задача project selection (она же maximum weight closure). Сводится к минимальному разрезу.
Построение сети. Исток $s$, сток $t$. Для каждого проекта $i$ с прибылью $p_i$:
- если $p_i > 0$ — ребро $s \to i$ пропускной $p_i$;
- если $p_i < 0$ — ребро $i \to t$ пропускной $|p_i|$;
- зависимость «$i$ требует $j$» — ребро $i \to j$ пропускной $\infty$.
Пусть $P = \sum_{p_i>0} p_i$ — сумма всех положительных прибылей. Тогда: $$\text{максимальная прибыль} = P - \text{mincut}(s,t).$$
Почему работает. Бесконечные рёбра зависимостей делают невозможным «разрезать» зависимость — значит в части $S$ (со стороны истока, выбранные проекты) лежат только замкнутые относительно зависимостей множества. Минимальный разрез отрезает либо «упущенную прибыль» (не взяли плюсовой проект — режем ребро $s\to i$), либо «обязательный убыток» (взяли минусовой — режем $i\to t$). Минимизируя сумму отрезанного, максимизируем чистую прибыль.
long long P = 0;
for(int i=0;i<n;i++){
if(p[i] > 0){ P += p[i]; add_edge(s, i, p[i]); }
else if(p[i] < 0) add_edge(i, t, -p[i]);
}
for(auto&[i,j]:deps) add_edge(i, j, INF); // i требует j
long long answer = P - maxflow(s, t);
Восстановление выбранных проектов: после maxflow — это вершины, достижимые из $s$ в остаточной сети (множество $S$ минимального разреза).
Грабли: INF для рёбер зависимостей берите достаточно большим (больше суммы всех |p|), но не LLONG_MAX — иначе при сложении в потоке переполнение. Все веса — long long.
Это частный случай более общей задачи maximum weight closure на ориентированном графе: выбрать замкнутое (по исходящим рёбрам) подмножество вершин с максимальной суммой весов. Стандартный приём — ровно тот, что описан: плюсовые веса вешаем на $s$, минусовые на $t$, рёбра графа делаем бесконечными, считаем $P - \text{mincut}$. Распознать такую задачу на олимпиаде помогает формулировка вида «если берём X, обязаны взять Y» вместе с прибылями/штрафами — почти всегда это min-cut. Если зависимости двусторонние или есть взаимоисключения, конструкция усложняется, но ядро то же.