双対！（素振り）
二変数の差に関する制約なので、これは双対ゲーです（断言）
まずは双対について調べます
双対性
tokoharuland.hateblo.jp
行間が広すぎて、死ぬ
僕が3時間くらい努力すると、最小循環費用流の双対で解ける問題は以下のように定式化できます
主問題
min sum w_e f_e
s.t.
l_e ≤ f_e ≤ u_e
sum_{e \in vに入る辺} f_e - sum_{e \in vから出る辺} f_e = 0
f ≥ 0
双対問題
max sum (l_e a_e - u_e b_e)
s.t.
a_e - b_e + p_y - p_x ≤ w_e, e = xy
a ≥ 0, b ≥ 0, p ≥ 0
ここで、
lは最小流量制約、
uは最大流量制約、
a, bはスラック変数、
p_vはポテンシャル、
w_eは最小費用流のコストです
また、aとbはどちらか片方だけ使います（両方同時に使えるかは考え中）
双対問題の解（=主問題の解）を求めるためには、lとuとwに合わせて辺を張ればいいです。
具体的には、aは最小流量lでコストwの辺を、bは最大流量uでコストwの辺を、xからyに向かって貼ればいいです
最小流量はINFでなんとかします 参考：
sigma425.hatenablog.com
さて、元の問題にもどると、条件は以下のように書き下すことができます
min sum b_e
s.t.
- b_e + A_y - A_x ≤ L_e - 1, e = xy
1 ≤ A_i ≤ 3
b ≥ 0, A ≥ 0
ここで、Lは問題文で与えられたlのことを表します（アルファベット、足りん！w）
まず、minをmaxに変形します これは単に-1倍すればいいです
min sum b_e ⇔ max sum - b_e
この変形から u_e = 1 、つまり最大流量が1であることがわかります
次に 1 ≤ A_i ≤ 3 の制約をなんとかします これは新たに変数を追加して無理やり二変数の関係にします
新たに超頂点Vのポテンシャルを表す変数 Z = 0 を追加することにしたとすると
A_i - Z ≤ 3
Z - A_i ≤ -1
となります。さらに、スラック変数を追加して
-c_i + A_i - Z ≤ 3
-d_i + Z - A_i ≤ -1
と変形します。このときc_i とd_i は常に0であってほしいので、目的関数における係数をINFにします。
すると、V から i に流量INF、コスト3の辺、i から V に流量INF、コスト-1の辺が貼られることになります。
あとは最小循環費用流を流すことでこの問題を解くことができました。
出力の際、目的関数を-1倍したことに注意してください。
最小循環費用流については以下のブログが参考になります。
snuke.hatenablog.com
実装例
atcoder.jp
ほんへ
2019/10/15 追記
1 ≤ A_i ≤ 3 は 0 ≤ A_i ≤ 2 と同値なのに気がつくと負辺が半分以下になるのでかなり定数倍がよくなります。
radix heap なんてなかった
atcoder.jp
