⾝為⼀個成熟的⼤學⽣，想要在校園裡舒適的⽣活，勢必要向各⽅勢⼒繳納⾼額的保護費，你繳的越多，你的⼤學
⽣活就會越安穩。
現在你⾝為⼀位國立清寒⼤學的新⽣，進到學校的第⼀件事當然是想辦法繳保護費。你知道學校裡有多⽅勢⼒盤
據，且你的學校是可以⽤⼀張簡單無向圖$G$來表⽰，每個節點都是⼀個領地且⼀定會被恰⼀⽅勢⼒所佔據，領地
之間有⼀些邊互相連接。如果你不⼩⼼同時繳納保護費給兩個勢⼒且有⼀條邊橫跨兩⽅勢⼒的領地，他們將會發⽣
衝突，⽽你將非常慘。
所以繳納保護費也是⼀件充滿學問的⼤事，⼀個不⼩⼼就會讓你的⼤學⽣活陷入悲劇。
清寒⼤學裡總共有$K$⽅勢⼒，編號由$1$到$K$。想要請第$t$⽅勢⼒保護你，就必須繳納$c_t$⾦額的保護費。
因為你認為繳的越多就得到越多，所以請你求出在不發⽣衝突的情況下，你最多可以繳納多少保護費。
第一行輸入三個非負整數$N$, $M$,$K$, 代表無向圖$G$ 的點數,邊數,和學校中的勢力個數
第二行輸入$N$個正整數$a_1, a_2, \dots , a_N$ 分別代表$i$節點的勢力
在接下來的$M$行中,每行包含兩個正整數$u_i, v_i$代表第$i$條邊連接著$G$上$u_i$, $v_i$兩點
最後一行輸入$K$個正整數$c_1, c_2, \dots , c_K$分別表示$i$號勢力所收取的保護費金額
輸出⼀個整數，代表不發⽣衝突的情況下，能繳納的保護費⾦額最⼤值。
5 4 3 1 2 1 2 3 1 2 2 3 3 4 4 5 1 3 3
4
$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq a_i \leq K ( 1 \leq i \leq N)$
$1 \leq u_i, v_i \leq N ( 1 \leq i \leq M)$
$ 1 \leq c_i \leq 10^9 (1 \leq i \leq K)$
保證沒有自環
$50\%$測資$K\leq 20$
$100\%$測資$K\leq 44$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||