8210: [yosupo] Graph - Minimum Cost b-flow
[Creator : ]
Description
You are given a directed graph with $n$ vertices and $m$ edges, amount of supply/demand associated with each vertex, and flow lower/upper bound associated with each edge.The $v$-th vertex has $b_v$ amount of supply if $b_v$ was positive, and $-b_v$ amount of demand otherwise.The $e$-th edge is directed from vertex $s_e$ to $t_e$ and has flow lower bound $l_e$, flow upper bound $u_e$, and cost per a unit of flow $c_e$.
Your task is to find and print the minimum cost $\mathbf{b}$-flow value $z$, the flow $\mathbf{f}$ and its dual $\mathbf{p}$ that achives the minimum, that is, $z$, $\mathbf{f} =\{f_e\}_{e = 0 \dots m-1}$, and $\mathbf{p} =\{p_v\}_{v = 0 \dots n-1}$ that satisfies following constraints;
If there's no such values, output "infeasible" instead.
Your task is to find and print the minimum cost $\mathbf{b}$-flow value $z$, the flow $\mathbf{f}$ and its dual $\mathbf{p}$ that achives the minimum, that is, $z$, $\mathbf{f} =\{f_e\}_{e = 0 \dots m-1}$, and $\mathbf{p} =\{p_v\}_{v = 0 \dots n-1}$ that satisfies following constraints;
-
$z = \sum_{e} c_e f_e$
-
$l_e \leq f_e \leq u_e$ (Capacity constraints)
-
$\sum{e \in \delta^+(v)} f_e - \sum{e \in \delta^-(v)} f_e = b_v$ (Flow conservation constraints)
-
$f_e \gt l_e \Rightarrow c_e + p{s_e} - p{t_e} \le 0$ (Complementary slackness conditions)
-
$f_e \lt u_e \Rightarrow c_e + p{s_e} - p{t_e} \ge 0$ (Complementary slackness conditions)
-
$|p_v| \le @{param.P_MAX}$
If there's no such values, output "infeasible" instead.
Input
$n$ $m$
$b_0$
$\vdots$
$b_{n-1}$
$s_0$ $t_0$ $l_0$ $u_0$ $c_0$
$\vdots$
$s_{m-1}$ $t_{m-1}$ $l_{m-1}$ $u_{m-1}$ $c_{m-1}$
$b_0$
$\vdots$
$b_{n-1}$
$s_0$ $t_0$ $l_0$ $u_0$ $c_0$
$\vdots$
$s_{m-1}$ $t_{m-1}$ $l_{m-1}$ $u_{m-1}$ $c_{m-1}$
Output
If the problem was infeasible output a single line
. Otherwise,
$z$
$p_0$
$\vdots$
$p_{n-1}$
$f_0$
$\vdots$
$f_{m-1}$
infeasible
. Otherwise,
$z$
$p_0$
$\vdots$
$p_{n-1}$
$f_0$
$\vdots$
$f_{m-1}$
Constraints
$0 \le n \leq 100$
$0 \le m \leq 1,000$
$0 \le s_e \lt n$
$0 \le t_e \lt n$
$|b_v| \le 10^9$
$|l_e| \le 10^9$
$|u_e| \le 10^9$
$|c_e| \le 10^9$
$l_e \le u_e$
All of the values are integral
$0 \le m \leq 1,000$
$0 \le s_e \lt n$
$0 \le t_e \lt n$
$|b_v| \le 10^9$
$|l_e| \le 10^9$
$|u_e| \le 10^9$
$|c_e| \le 10^9$
$l_e \le u_e$
All of the values are integral
Sample 1 Input
3 5
1
-1
0
0 1 1 2 1
1 2 0 2 2
2 0 -3 5 1
0 2 0 3 -2
2 1 0 1 0
Sample 1 Output
-2
0
-1
-1
1
0
3
3
0
Sample 2 Input
2 1
-1
1
0 0 -1 1 0
Sample 2 Output
infeasible
Sample 3 Input
2 1
1
0
0 1 -10 10 0
Sample 3 Output
infeasible