c812 - 1. 觀光景點
題目描述
題目要求計算在一個給定的觀光景點網絡中，與指定景點 v 的相關性至少為 q 的景點數量。網絡由 n 個景點和 n-1 條邊組成，每條邊都有一個相關性值 r。相關性定義為兩個景點之間路徑上最小的相關性值。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。首先，將觀光景點網絡表示為一個鄰接表。然後，從起始景點 v 開始進行 DFS，遍歷所有可達的景點。在 DFS 過程中，記錄從起始景點到每個景點的路徑上的最小相關性值。如果這個最小值大於或等於 q，則將該景點計入結果。為了避免重複計算，使用一個 used 陣列來標記已經訪問過的景點。
複雜度分析
- 時間複雜度: O(N + E)，其中 N 是景點數量，E 是邊的數量。在最壞情況下，DFS 需要訪問所有景點和邊。
- 空間複雜度: O(N)，主要用於儲存鄰接表和
used陣列。
程式碼
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int s,ans,x,y,iv,n,v,q;
bool used[5010];
struct road{
int rv;
int g;
};
map <int,vector <road> > p;
void dfs(int no,int mv){
if(used[no])return;
used[no]=1;
if(mv<q)return;
if(no!=v)++ans;
for(int i=0;i<p[no].size();++i)
dfs(p[no][i].g,min(mv,p[no][i].rv));
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> v >> q;
for(int i=0;i<n-1;++i){
cin >> x >> y >> iv;
road tmp,tmp2;
tmp.g=y;
tmp2.g=x;
tmp2.rv=tmp.rv=iv;
p[x].push_back(tmp);
p[y].push_back(tmp2);
}
for(int i=0;i<p[v].size();++i)
dfs(p[v][i].g,p[v][i].rv);
cout << ans << "\n";
}