I - Maximum Profits by Toll
Ceylon
5
s
1024
MB
100
点
問題文
彩国には、 $1$ から $N$ の番号が付いた $N$ 個の町があり、町を結ぶ $M$ 本の道があります。
$j (1 \le j \le M)$ 番目の道は、町 $u_j$ から町 $v_j$ へ向かう一方通行の道路です。
それぞれの道について、今年は $t_j$ 人通るというデータが求まっています。
国王である Asa さんは、それぞれの道に対して、非負整数の通行料 $f_j$ 円を設定することで、利益を生み出そうと考えました。
彩国の住民は 1 度決めたら行動を変えないため、 $t_j$ は $f_j$ によって変化しません。
しかし、それぞれの町長は、その町に入るための通行料が高くなってしまうと観光客が減ってしまうと恐れ、 Asa さんに以下の条件を満たすように求めました。
- すべての町 $i (1 \le i \le N)$ について、 $X$ をほかの町から町 $i$ へ向かう道路の集合、 $Y$ を町 $i$ からほかの町へ向かう道路の集合としたとき、以下の条件を満たす。
$$\sum_{j \in X} f_j \le c_i + \sum_{j \in Y} f_j$$- なお、 $c_i$ は入力で与えられる非負整数である
Asa さんは、町長から求められた条件を満たすように通行料を設定することで、利益 $\sum_{j=1}^{M} t_j f_j$ を最大化したいと考えています。
Asa さんが得られる利益の最大値を求めてください。
制約
- $2 \le N \le 2 \times 10^5$
- $1 \le M \le \min(N (N-1), 2 \times 10^5)$
- $1 \le u_j, v_j \le N$
- $u_j \ne v_j$
- $j \ne j' \Rightarrow (u_j, v_j) \ne (u_{j'}, v_{j'})$
- $1 \le t_j \le 10^4$
- $0 \le c_i \le 10^4$
- 入力はすべて整数である
部分点
- (5 点) すべての $i$ について $c_i = 0$
- (10 点) 与えられる町と道路の情報は、有向木として表現できる。つまり、以下の 2 条件を同時に満たす。
- $M = N - 1$ である
- 根となる町 $r$ を適切に選ぶことで、 $r$ からすべての町に到達可能である
- (85 点) 追加の制約はない
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$
$c_1$ $c_2$ ... $c_N$
$u_1$ $v_1$ $t_1$
$u_2$ $v_2$ $t_2$
...
$u_M$ $v_M$ $t_M$
$c_1$ $c_2$ ... $c_N$
$u_1$ $v_1$ $t_1$
$u_2$ $v_2$ $t_2$
...
$u_M$ $v_M$ $t_M$
出力
Asa さんが得られる利益の最大値を出力せよ。
利益をいくらでも大きくすることができる場合は、 -1 を出力せよ。
入力例 1
6 6
1 1 1 1 1 1
1 2 1
1 3 1
2 4 1
2 5 1
3 5 1
5 6 1
出力例 1
9
与えられる町と道の情報は、以下のようになります。
以下のように通行料を設定することで、条件を満たしながら利益を最大化することができます。
この入力は、小課題 3 の制約を満たします。
入力例 2
3 2
1 1 1
1 2 1
2 3 1
出力例 2
3
この入力は、小課題 2, 3 の制約を満たします。
入力例 3
6 6
0 0 0 0 0 1
1 2 1
1 3 1
2 4 10000
3 5 1
4 6 1
5 6 100
出力例 3
10002
この入力は、小課題 3 の制約を満たします。