New answers tagged

7

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.


1

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 ...


2

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