n689 - pD. 技能點數
題目描述
題目描述了一個技能解鎖系統，其中技能之間存在相依關係。給定技能總數 N，技能相依關係 M，以及已購買的技能書 K，要求計算可以解鎖的技能總數，包括技能書本身。
解題思路
本題可以視為一個有向圖的問題，其中節點代表技能，邊代表技能相依關係。已購買的技能書相當於初始解鎖的節點。解題思路是從已解鎖的技能出發，遍歷圖，解鎖所有可以解鎖的技能。
程式碼使用了一個鄰接矩陣 g 來表示技能相依關係。has 陣列用於標記已解鎖的技能。b 陣列儲存已購買的技能書。ct 陣列儲存每個技能被依賴的數量。
程式首先將已購買的技能書標記為已解鎖。然後，遍歷所有已解鎖的技能，如果該技能依賴的技能尚未解鎖，則解鎖該技能，並更新 ct 陣列。這個過程重複進行，直到沒有新的技能可以解鎖。
複雜度分析
- 時間複雜度: O(N^2)
- 空間複雜度: O(N^2)
程式碼
#include <iostream>
using namespace std;
bool g[1001][1001],has[1001];
int b[1001],ct[1001];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
int n,m,k,ans=0;
cin >> n >> m >> k;
for(int i = 0; i < k; i++){
cin >> b[i];
has[b[i]] = 1;
}
for(int i = 0; i < m; i++){
int a,b;
cin >> a >> b;
g[a][b] = 1;
++ct[b];
}
ans=k;
for(int i = 0; i < k; i++){
for(int j=0;j<n;++j){
if(g[b[i]][j]&&!has[j]){
g[b[i]][j] = 0;
--ct[j];
if(ct[j]==0){
b[ans++]=j;
}
}
}
}
for(int i=k;i<ans;++i){
for(int j=0;j<n;++j){
if(g[b[i]][j]&&!has[j]){
g[b[i]][j] = 0;
--ct[j];
if(ct[j]==0){
b[ans++]=j;
}
}
}
}
cout << ans;
}