최소 비용 b-유량

$\gdef\relmiddle#1{\mathrel{}\middle#1\mathrel{}}$

$n$개의 정점과 $m$개의 간선을 가진 유향 그래프, 각 정점에 대응하는 공급량/수요량, 그리고 각 간선에 대응하는 유량 하한/상한이 주어진다. $b_v$가 양수이면 $v$번째 정점의 공급량은 $b_v$이고, 그렇지 않으면 수요량은 $-b_v$이다. $e$번째 간선은 정점 $s_e$에서 $t_e$로 향하며, 유량 하한은 $l_e$, 유량 상한은 $u_e$, 단위 유량당 비용은 $c_e$이다.

해야 할 일은 최소 비용 $\mathbf{b}$-유량 값 $z$와 그 최솟값을 달성하는 유량 $\mathbf{f}$ 및 그 쌍대해 $\mathbf{p}$을 찾아 출력하는 것이다. 즉, 다음 제약 조건을 만족하는 $z$, $\mathbf{f} = \lbrace f_e\rbrace _ {e = 0 \dots m-1}$, $\mathbf{p} = \lbrace p_v\rbrace _ {v = 0 \dots n-1}$을 찾아 출력한다.

• $z = \sum_{e} c_e f_e$
• $l_e \leq f_e \leq u_e$ (용량 제약 조건)
• $\sum_{e \in \delta^+(v)} f_e - \sum_{e \in \delta^-(v)} f_e = b_v$ (유량 보존 제약 조건)
• $f_e \gt l_e \Rightarrow c_e + p_{s_e} - p_{t_e} \le 0$ (상보적 느슨성 조건)
• $f_e \lt u_e \Rightarrow c_e + p_{s_e} - p_{t_e} \ge 0$ (상보적 느슨성 조건)
• $|p_v| \le 1000000000000000$

여기서 $\delta^+(v)$은 정점 $v$에서 나가는 간선의 집합이고, $\delta^-(v)$은 정점 $v$으로 들어오는 간선의 집합이다. 즉, $\delta^+(v) = \left\lbrace e \relmiddle| s_e = v \right\rbrace$ 및 $\delta^-(v) = \left\lbrace e \relmiddle| t_e = v \right\rbrace$이다.

그러한 값들이 존재하지 않으면 대신 "infeasible"을 출력한다.

제약 조건

• $0 \le n \leq 100$
• $0 \le m \leq 1000$
• $0 \le s_e \lt n$
• $0 \le t_e \lt n$
• $|b_v| \le 1000000000$
• $|l_e| \le 1000000000$
• $|u_e| \le 1000000000$
• $|c_e| \le 1000000000$
• $l_e \le u_e$
• 모든 값은 정수이다

다음에 유의한다.

• 입력 그래프에는 자기 루프가 포함될 수 있다.
• 또한 결과 값은 $2^{64}$을 초과할 수 있다.

$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}$

문제가 실행 불가능하면 한 줄에 다음을 출력한다.

infeasible

. 그렇지 않으면,

$z$
$p_0$
 $\vdots$
$p_{n-1}$
$f_0$
 $\vdots$
$f_{m-1}$