n689. pD. 技能點數
Tags : 拓樸
Accepted rate : 7人/9人 ( 78% ) [非即時]
評分方式:
Tolerant

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

Content

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

已知全部技能有 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,
雖然本身沒有任何前置技能,但因沒有受到所購買的技能書觸發,因此不會主動被解鎖。

Input

第一行有三個正整數 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

Output

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

Sample Input #1
9 8 3
1 2 3
0 1
1 5
2 3
3 4
5 4
4 7
6 8
7 8
Sample Output #1
6
測資資訊:
記憶體限制: 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
Hint :

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

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

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」