k186. pC. 關卡地圖 (game)
Tags : 動態規劃 圖論 樹直徑 水母圖
Accepted rate : 14人/23人 ( 61% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-03-22 00:03

Content

題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing

許多遊戲的設計是以關卡為單位,玩家通過一個關卡後才能挑戰下一個關卡。這些關卡的解鎖關係有時並不是線性的,也就是玩家通過一個關卡後可能一次開放多個可以挑戰的新關卡,也可能不會開放任何新關卡。


經典的A遊戲就屬於這種非線性的關卡結構。關卡的狀態分為三種:「尚未解鎖」、「已解鎖但未通過」以及「已通過」。A遊戲有 $n$ 個關卡,被呈現在一張地圖上,其中有 $m$ 對關卡存在相互解鎖關係,以 $(u_i, v_i)$ 表示。當玩家通過關卡 $u_i$ 時,關卡 $v_i$ 將被解鎖;反過來說,當玩家通過關卡 $v_i$ 時,關卡 $u_i$ 也會被解鎖。玩家可以從任意關卡開始遊戲,且保證在非線性的玩法下,可以通過其他所有關卡。另,為了避免破關流程過於簡單,A遊戲滿足 $m ≤ n$ 。


凱特決定把A遊戲當作線性解鎖關卡來玩:選擇一個起始關卡,接著一旦通過了某個關卡 $c$ 後,下一關只能是與關卡 $c$ 有相互解鎖關係的關卡,且一關最多只能通過一次。已知凱特通過關卡 $i$ 時,得到的成就感為 $a_i$,請幫他找出最適合的破關路徑以最大化成就感總和。
舉例來說,假設A遊戲的關卡地圖如下圖所示,圖中圓點中的數字代表關卡編號,圓點旁邊的數字代表該關卡破關所得到的成就感;兩個關卡的連線代表一個相互解鎖關係。若凱特選擇從關卡 $7$ 開始破關,則關卡 $5$ 將被解鎖,接著依序通過關卡 $5, 1, 3, 6, 2$,得到的成就感總和為 $4 + (−3) + (−1) + 3 + 0 + 2 = 5$。另一方面,若凱特選擇從關卡 $8$ 開始破關,並依序通過關卡 $6, 3, 1, 2$,得到的成就感總合為 $2 + 0 + 3 + (−1) + 2 = 6$,此時成就感總和為最大值。

測資限制

•    $1 ≤ n ≤ 10^5$。
•    $m = n − 1$ 或 $m = n$。
•    $1 ≤ u_i < v_i ≤ n$,且若 $i \ne j$,保證 $(u_i, v_i) \ne (u_j , v_j )$。
•    $-10^9 ≤ a_i ≤ 10^9$。
•    遊戲設計保證正常遊玩(非線性)時從任何一關做為起始關卡皆能解鎖所有關卡。
•    上述變數都是整數。

Input
$n$ $m$
$u_1$ $v_1$
$u_2$ $v_2$
...
$u_m$ $v_m$
$a_1$ $a_2$ . . . $a_n$

•    $n$ 代表關卡數。
•    $m$ 代表解鎖關係數。
•    $u_i, v_i$ 代表通過關卡 $u_i$ 或 $v_i$ 的其中一個後,另一個關卡將被解鎖。
•    $a_i$ 代表凱特通過關卡 $i$ 時的成就感。

Output
$s$

•   $s$ 為一整數,代表凱特能獲得的最大成就感總和。

Sample Input #1
8 8
6 8
3 6
2 6
1 3
1 2
1 4
1 5
5 7
-1 2 3 -10 -3 0 4 2
Sample Output #1
6
Sample Input #2
2 1
1 2
-1 -10
Sample Output #2
-1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (2%): 1.0s , <1M
公開 測資點#1 (3%): 1.0s , <1M
公開 測資點#2 (3%): 1.0s , <1M
公開 測資點#3 (3%): 1.0s , <1M
公開 測資點#4 (3%): 1.0s , <1M
公開 測資點#5 (3%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (6%): 1.0s , <10M
公開 測資點#9 (6%): 1.0s , <10M
公開 測資點#10 (6%): 1.0s , <10M
公開 測資點#11 (4%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (8%): 1.0s , <10M
公開 測資點#18 (9%): 1.0s , <10M
公開 測資點#19 (9%): 1.0s , <10M
Hint :

題目和測資來源 : twpca

注意因為礙於系統問題測試資料沒辦法完整的放上來,所以也許會有測資不夠強的狀況,歡迎提出。

 

子任務 分數 額外輸入限制測資點
117$n ≤ 100$#00~#05
223$m = n − 1$#06~#09
334$a_i ≥ 0$#10~#16
426無額外限制#17~#19

 

如果題目有問題歡迎來信詢問!

Tags:
動態規劃 圖論 樹直徑 水母圖
出處:
TOI入營考2023 [管理者: Ststone1687 (Ststone) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
39475 asdfasdfasdf ... (unknown) k186
RE
65 2024-02-25 21:29