n689. pD. 技能點數 - 高中生程式解題系統

內容

在遊戲中有許多技能，
而技能間可能存在相依關係，也就是必須先解鎖前置技能，才能夠解鎖後面技能；
或者也可以購買技能書，就能夠忽略前置技能是否解鎖，而提前進到下個技能階段。

已知全部技能有 N 個(編號 0 ~ N-1)，
以及 M 組技能相依關係 (u, v)，也就是需要先解鎖技能 u 才能解鎖技能 v

假設現在購買了 K 本技能書 (a₁, a₂, ..., a_K)，
請協助計算包含初始技能書本身技能在內，最後總共可以解鎖幾種不同的技能。

以下圖為例，假設全部技能有 9 個，並購買了技能 {1, 2, 3} 的技能書，
則最後總共可以解鎖 {1, 2, 3, 4, 5, 7} 共六種不同的技能

其中特別的是，對於技能 0 和技能 6，
雖然本身沒有任何前置技能，但因沒有受到所購買的技能書觸發，因此不會主動被解鎖。

輸入說明

第一行有三個正整數 N, M, K，
代表總技能數、技能相依關係數、已購買技能書數
1 ≤ N ≤ 1000
N-1 ≤ M ≤ 2*N
1 ≤ K ≤ 10

接著有 K 個數字 a_i，代表已購買的技能書技能編號
0 ≤ a_i ≤ N-1

最後有 M 行，每行有兩個整數 u 和 v，
代表需要先解鎖技能 u 才能解鎖技能 v
0 ≤ u,v ≤ N-1

輸出說明

包含初始技能書本身技能在內，
最後總共可以解鎖幾種不同的技能

範例輸入 #1

範例輸出 #1

測資資訊：

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

提示：

10%：為直鏈，即相依關係為 (0, 1), (1, 2), ..., (N-2, N-1)
30%：K ≤ 3
60%：無特別限制

標籤:

拓樸

出處:

113學年度 hgsh 校內賽 [管理者： mushroom.cs9 ... (mushroom) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」