L - Kyosan Escalator
問題文
京都産業大学は山の斜面に建設されているので、構内の様々な場所にエスカレーターがあります。未来の京都産業大学では、各エスカレーターに利用料が設定されています。また、各エスカレーターには月間維持費というものも設定されています。
京都産業大学の地点の数 $N$、地点間を結ぶ道またはエスカレーターの合計 $M$、利用料から得られる月間収益 $P_i$ ($1 \leq i \leq M$), 月間維持費 $C_i$ ($1 \leq i \leq M$ )が与えられます。また、月間利益は $P_i - C_i$ で計算されます。
各地点間を結ぶ道またはエスカレーターは辺 $(u_i, v_i)$ で結ばれており、双方向に通行可能です。また、$C_i = P_i = 0$ のときに限り、辺 $(u_i, v_i)$ は道です。道の場合、月間収益と月間維持費はともに $0$ 円です。
理事長である寺子さんは月間利益を最大化するために、いくつかのエスカレーターを取り壊すことにしました。ただし、エスカレーターを取り壊すことで行けなくなる地点が出てはいけません。
適切にエスカレーターを取り壊すとき、残ったエスカレーターから得られる月間利益の合計を出力してください。(エスカレーターを取り壊すことで、他のエスカレーターの月間利益と月間維持費は変化しないものとします)
制約
- $2 \leq N \leq 10^5$
- $N-1 \leq M \leq min(\tfrac{N(N-1)}{2}, 10^5)$
- $1 \leq u_i < v_i \leq N$
- $0 \leq P_i \leq 10^5$
- $0 \leq C_i \leq 10^5$
- 初め、任意の2つ地点は、道またはエスカレーターを通って到達可能
入力
$N~~M$
$u_1~~v_1$$~~P_1$$~~C_1$
$u_2~~v_2$$~~P_2$$~~C_2$
$\vdots$
$u_M~~v_M$$~~P_M$$~~C_M$
出力
1行出力せよ。
1行目には残ったエスカレーターから得られる月間利益の合計を出力せよ。
7 8
1 2 0 0
1 3 5 10
3 4 1 2
4 5 3 2
5 6 0 0
3 6 0 0
6 7 9 3
2 7 0 0
7
利益がマイナスなのは2番目と3番目に与えられたエスカレーターで、両方を取り壊してもいけなくなる地点は存在しません。残ったエスカレーターは4番目と7番目で、それぞれ利益は1と6なので、合計の7を出力します。