New answers tagged


If such an orientation is possible, then all degrees are even. Conversely, if all degrees are even then the graph is Eulerian. Orient the edges according to an Eulerian circuit.


Observe that if $v$ is not a vertex of $p$, then $f_p(u,v)=0$. When $v$ is in $p$ and not a source nor a sink, then there are only two vertices $v_1$ and $v_2$ such that the edges $(v_1,v),(v,v_2)$ are in $p$. Therefore, in the excess flow at $v$ $$\sum_u f_p(u,v)$$ only has two non-zero terms $f_p(v_1,v)=c_f(p)$ and $f_p(v_2,v)=-f_p(v,v_2)=-c_f(p)$. So, the ...


This is straight up a minimum-cost flow problem. All it's missing is a an edge from the source to each porter with zero cost and capacity equal to the porter, and a zero cost edge from each urn to the sink with capacity equal to that urn.

Top 50 recent answers are included