0w1

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;
}