最小费用流（Minimum Cost b-flow）

问题描述

给定一个含 $n$ 个顶点、$m$ 条边的有向图，每条边 $e$ 有：

• 流量下界 $l_e$、上界 $u_e$，
• 单位流量费用 $c_e$。

每个顶点 $v$ 有供需量 $b_v$：若 $b_v > 0$，表示供应 $b_v$ 单位；若 $b_v < 0$，表示需求 $-b_v$ 单位。

求满足以下条件的最小费用可行流 $\mathbf{f} = (f_e)_{e=0}^{m-1}$ 与对偶势 $\mathbf{p} = (p_v)_{v=0}^{n-1}$：

1. 容量约束：$l_e \le f_e \le u_e$
2. 流量守恒：对每个顶点 $v$，$$\sum_{e \in \delta^+(v)} f_e - \sum_{e \in \delta^-(v)} f_e = b_v$$
3. 互补松弛条件（最优性条件）：
   • 若 $f_e > l_e$，则 $c_e + p_{s_e} - p_{t_e} \le 0$
   • 若 $f_e < u_e$，则 $c_e + p_{s_e} - p_{t_e} \ge 0$

目标是最小化总费用：

若不存在可行流，输出 infeasible；否则输出：

• $z$（最小费用）
• 势 $p_0, p_1, \dots, p_{n-1}$
• 流量 $f_0, f_1, \dots, f_{m-1}$

约束条件

• $0 \le n \le 100$
• $0 \le m \le 1000$
• $0 \le s_e, t_e < n$
• $|b_v|, |l_e|, |u_e|, |c_e| \le 10^9$
• $l_e \le u_e$
• 所有值为整数
• 输入图可含自环
• 结果可能超过 $2^{64}$

输入格式

$n\ m$
$b_0$
$b_1$
:
$b_{n-1}$
$s_0\ t_0\ l_0\ u_0\ c_0$
$s_1\ t_1\ l_1\ u_1\ c_1$
:
$s_{m-1}\ t_{m-1}\ l_{m-1}\ u_{m-1}\ c_{m-1}$

输出格式

• 若不可行:

  infeasible

• 否则:

  $z$
  $p_0\ p_1\ \cdots\ p_{n-1}$
  $f_0\ f_1\ \cdots\ f_{m-1}$

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

-2
0
-1
-1
1
0
3
3
0

2 1
-1
1
0 0 -1 1 0

infeasible

2 1
1
0
0 1 -10 10 0

infeasible