Как задать пропускную способность на вершине (vertex capacity) в задаче о потоке?

Приём «расщепление вершины» (vertex splitting). Каждую вершину $v$ с пропускной способностью $cap_v$ заменяем на две: $v_{in}$ и $v_{out}$, соединённые ребром $v_{in} \to v_{out}$ с пропускной способностью $cap_v$.

Правило перенаправления рёбер:

• все рёбра, входившие в $v$, теперь входят в $v_{in}$;
• все рёбра, выходившие из $v$, теперь выходят из $v_{out}$.

Теперь весь поток, проходящий через $v$, обязан пройти по «внутреннему» ребру $v_{in}\to v_{out}$, и его пропускная способность $cap_v$ ограничивает поток через вершину. Дальше — обычный max-flow.

// нумерация: vin(v) = 2*v, vout(v) = 2*v+1
for(int v=0; v<V; v++) add_edge(2*v, 2*v+1, capVertex[v]); // ребро вершины
for(auto&[u,w,c]:origEdges) add_edge(2*u+1, 2*w, c);       // u_out -> w_in
int flow = maxflow(2*s+1, 2*t); // источник — это s_out, сток — t_in

Размер сети удваивается по вершинам ($2V$) и добавляется $V$ рёбер — это $O(V)$ накладных расходов, асимптотика алгоритма не меняется. Этот приём — основа множества задач: «максимум вершинно-непересекающихся путей» (теорема Менгера), задачи с лимитами на узлы сети и т.п.