n689. pD. 技能點數
標籤 : 拓樸
通過比率 : 19人/24人 ( 79% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-16 18:50

內容

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

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

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

以下圖為例,假設全部技能有 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 個數字 ai,代表已購買的技能書技能編號
0 ≤ ai ≤ N-1

最後有 M 行,每行有兩個整數 u 和 v,

代表需要先解鎖技能 u 才能解鎖技能 v
0 ≤ u,v ≤ N-1

輸出說明

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

範例輸入 #1
9 8 3
1 2 3
0 1
1 5
2 3
3 4
5 4
4 7
6 8
7 8
範例輸出 #1
6
測資資訊:
記憶體限制: 512 MB
提示 :

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

標籤:
拓樸
出處:
113學年度hgsh校內賽 [管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

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