Project selection / задача о выборе проектов — как свести максимизацию прибыли к минимальному разрезу?

Это каноническая задача 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$ — сумма всех положительных прибылей. Тогда:

Почему работает. Бесконечные рёбра зависимостей делают невозможным «разрезать» зависимость — значит в части $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.