UVA 1267 Network ( DFS )
把需要被覆蓋的節點押進該深度的節點表裡,之後依次選擇深度最深的為覆蓋的節點,用貪婪的思維找尋其 k級祖先設置伺服器。注意題目只要求葉節點覆蓋。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000 + 3; int n, s, k; vector<int> G[MAXN]; vector<int> depth2node[MAXN]; int pa[MAXN]; int vis[MAXN]; void dfs(int u, int fa, int d){ if( G[ u ].size() == 1 && d > k ) depth2node[ d ].push_back( u ); pa[ u ] = fa; for(int v: G[ u ]){ if( v == fa ) continue; dfs( v, u, d + 1 ); } } void dfs2(int u, int fa, int d){ if( d > k ) return; vis[ u ] = true; for(int v: G[ u ]){ if( v == fa ) continue; dfs2( v, fa, d + 1 ); } } void solve(){ dfs( s, -1, 0 ); int ans = 0; memset( vis, 0, sizeof(vis) ); for(int d = n - 1; d > k; --d) for(int u: depth2node[ d ]){ if( vis[ u ] ) continue; for(int j = 0; j < k; ++j) u = pa[ u ]; dfs2( u, -1, 0 ); ++ans; } printf("%d\n", ans); } void init(){ for(int i = 1; i <= n; ++i){ G[ i ].clear(); depth2node[ i ].clear(); } } int main(){ int T; scanf("%d", &T); while( T-- ){ scanf("%d", &n); scanf("%d%d", &s, &k); init(); for(int i = 0; i < n - 1; ++i){ int a, b; scanf("%d%d", &a, &b); G[ a ].push_back( b ); G[ b ].push_back( a ); } solve(); } return 0; }