No.748 yuki国のお財布事情
タグ : / 解いたユーザー数 144
作問者 : ikd / テスター : nanae
問題文
yuki国には$N$個の町と$M$本の道路があります。
道路で結ばれた町と町とは双方向に行き来することができます。
$2$つの町を結ぶ道路は$2$本以上存在せず、道路の両端が同じ町となることはありません。
どの町からどの町へもいくつかの道路をたどって行くことができます。
yuki国では毎年道路の維持費が各道路ごとに発生しています。
そこで王様であるあなたはいくつかの道路を閉鎖することを考えました。
閉鎖された道路を辿って町を行き来することはできなくなりますが、その道路にかかっていた費用の分だけ維持費が削減できます。
ただし国民からの反発を防ぐため、道路の閉鎖によって町から町へたどり着けなくなることがあってはいけません。
つまり道路閉鎖後においても、どの町からどの町へもいくつかの閉鎖されていない道路のみをたどって行くことができるようになっている必要があります。
さらに、yuki国の国民は$K$本の道路を指定し、これらの道路には思い入れがあるため閉鎖しないように要求しています。
あなたは国民の要求を呑みつつ、できるだけたくさん道路の維持費を削減したいと考えています。
削減できる維持費の総和の最大値はいくつでしょうか。
入力
$N$ $M$ $K$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ $.$ $.$ $a_M$ $b_M$ $c_M$ $e_1$ $e_2$ $.$ $.$ $e_K$
$1$行目に町の個数$N$、道路の本数$M$、yuki国の国民が指定した道路の本数$K$が空白区切りで与えられます。
$2$行目から$M$行にわたって道路の情報が与えられます。
そのうち$i$行目には道路$i$が結んでいる$2$つの町$a_i$および$b_i$、道路$i$の維持費$c_i$が空白区切りで与えられます。
$2+M$行目から$K$行にわたってyuki国の国民が指定した道路の情報が与えられます。
そのうち$i$行目には整数$e_i$が与えられます。これはyuki国の国民が道路$e_i$を閉鎖しないよう要求していることを意味します。
制約
- $1 \le N \le 10^5$
- $N-1 \le M \le \min(N\times(N-1)/2, 10^5)$
- $0 \le K \le M$
- $1 \le a_i < b_i \le N\ (i=1, 2, \dots, M)$
- $i \neq j$ならば$(a_i, b_i) \neq (a_j, b_j)$
- どの町からどの町へもいくつかの道路をたどって行くことができる
- $ 1 \le c_i \le 10^9\ (i=1, 2, \dots, M)$
- $1 \le e_1 < e_2 < \dots < e_K \le M$
- 入力はすべて整数
出力
削減できる維持費の総和の最大値を出力してください。最後に改行してください。
サンプル
サンプル1
入力
5 6 3 1 2 8 1 3 5 2 3 7 2 4 4 3 5 4 4 5 7 1 2 3
出力
7
道路$1, 2, 3$は国民の要求によって閉鎖できません。
道路$4, 5, 6$のうち、$2$つ以上閉鎖してしまうと町$4$や町$5$が孤立してしまいます。
この場合、道路$6$を閉鎖するのが最適です。道路$6$の維持費は$7$なので削減できる維持費の総和の最大値として$7$を出力します。
サンプル2
入力
4 5 0 1 2 5 1 3 3 1 4 1 2 3 2 2 4 3
出力
8
$K=0$の場合もありうることに注意してください。
道路$1$と、道路$2$または道路$5$を閉鎖することで合計$5+3=8$だけ維持費を削減することができます。
これが削減できる維持費の総和の最大なので$8$を出力します。
サンプル3
入力
6 11 6 4 5 15 2 5 14 2 6 10 1 6 15 3 6 11 2 3 18 5 6 12 1 4 4 2 4 6 1 2 17 3 5 6 1 3 6 7 10 11
出力
50
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。