Skip to main content
change notation to match the question
Source Link
Laakeri
  • 1.3k
  • 1
  • 10
  • 19

This problem can be solved with minimum-cost flow in polynomial time.

The flow network should should contain source and sink vertices $s$ and $t$, and for each vertex $v \in V$ two vertices, $v_{in}$ and $v_{out}$. The vertex $v_i$ should have an edge form $v_{in}$ to $v_{out}$ with capacity $b_i$ and cost $-3$. For each original edge $(u, v) \in E$$(u, v) \in A$, create an edge from $u_{out}$ to $v_{in}$ with capacity $\infty$ and cost $0$. For each $v$, create an edge from source $s$ to $v_{in}$ with capacity $\infty$ and cost $1$ and an edge from $v_{out}$ to sink $t$ with capacity $\infty$ and cost $1$.

Now in optimal flow, the cost will be $2 \cdot P -3 \cdot \sum b_i$, where $P$ is the optimal number of paths used.

This problem can be solved with minimum-cost flow in polynomial time.

The flow network should should contain source and sink vertices $s$ and $t$, and for each vertex $v \in V$ two vertices, $v_{in}$ and $v_{out}$. The vertex $v_i$ should have an edge form $v_{in}$ to $v_{out}$ with capacity $b_i$ and cost $-3$. For each original edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with capacity $\infty$ and cost $0$. For each $v$, create an edge from source $s$ to $v_{in}$ with capacity $\infty$ and cost $1$ and an edge from $v_{out}$ to sink $t$ with capacity $\infty$ and cost $1$.

Now in optimal flow, the cost will be $2 \cdot P -3 \cdot \sum b_i$, where $P$ is the optimal number of paths used.

This problem can be solved with minimum-cost flow in polynomial time.

The flow network should should contain source and sink vertices $s$ and $t$, and for each vertex $v \in V$ two vertices, $v_{in}$ and $v_{out}$. The vertex $v_i$ should have an edge form $v_{in}$ to $v_{out}$ with capacity $b_i$ and cost $-3$. For each original edge $(u, v) \in A$, create an edge from $u_{out}$ to $v_{in}$ with capacity $\infty$ and cost $0$. For each $v$, create an edge from source $s$ to $v_{in}$ with capacity $\infty$ and cost $1$ and an edge from $v_{out}$ to sink $t$ with capacity $\infty$ and cost $1$.

Now in optimal flow, the cost will be $2 \cdot P -3 \cdot \sum b_i$, where $P$ is the optimal number of paths used.

Source Link
Laakeri
  • 1.3k
  • 1
  • 10
  • 19

This problem can be solved with minimum-cost flow in polynomial time.

The flow network should should contain source and sink vertices $s$ and $t$, and for each vertex $v \in V$ two vertices, $v_{in}$ and $v_{out}$. The vertex $v_i$ should have an edge form $v_{in}$ to $v_{out}$ with capacity $b_i$ and cost $-3$. For each original edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with capacity $\infty$ and cost $0$. For each $v$, create an edge from source $s$ to $v_{in}$ with capacity $\infty$ and cost $1$ and an edge from $v_{out}$ to sink $t$ with capacity $\infty$ and cost $1$.

Now in optimal flow, the cost will be $2 \cdot P -3 \cdot \sum b_i$, where $P$ is the optimal number of paths used.