UVA1267 - Network

2021 단어
제목: n대와 그 연결은 하나의 트리 네트워크로 그 중에서 엽결점은 클라이언트이고 다른 결점은 서버이다.이미 한 서버가 VOD 서비스를 제공하여 최소 몇 개의 기억점에 서버를 설치하여 모든 클라이언트가 서버까지의 거리가 k를 초과하지 않도록 요구한다.
사고방식: 먼저 뿌리가 없는 나무를 뿌리가 있는 나무로 만든다.그 다음에 욕심을 이용하여 깊이가 가장 큰 결점 u를 찾아서 서버를 놓을 때마다 u의 k급 조상에 두는 것이 가장 수지가 맞는다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 1005;
vector<int> gr[MAXN], nodes[MAXN];
int n, s, k, fa[MAXN];
bool vis[MAXN];

void dfs(int u, int f, int d) {
    fa[u] = f;
    int nc = gr[u].size();
    if (nc == 1 && d > k)
        nodes[d].push_back(u);  // nodes 
    for (int i = 0; i < nc; i++)  {
        int v = gr[u][i]; 
        if (v != f) 
            dfs(v, u, d + 1);
    }
}

void dfs_cover(int u, int f, int d) {
    vis[u] = true;
    int nc = gr[u].size();
    for (int i = 0; i < nc; i++) {
        int v = gr[u][i]; 
        if (v != f && d < k)
            dfs_cover(v, u, d + 1);
    }
}

int solve() {
    int ans = 0;
    memset(vis, 0, sizeof(vis));
    for (int d = n - 1; d > k; d--)
        for (int i = 0; i < nodes[d].size(); i++) {
            int u = nodes[d][i];
            if (vis[u])
                continue;
            int v = u;
            for (int j = 0; j < k; j++)
                v = fa[v];
            dfs_cover(v, -1, 0);
            ans++;
        }
    return ans;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d%d", &n, &s, &k); 
        for (int i = 1; i <= n; i++) {
            gr[i].clear();
            nodes[i].clear();
        }
        for (int i = 0; i < n - 1; i++) {
            int a, b; 
            scanf("%d%d", &a, &b);
            gr[a].push_back(b);
            gr[b].push_back(a);
        }
        dfs(s, -1, 0);
        int ans = solve();
        printf("%d
", ans);
    }
    return 0;
}
MetaQ 안정성, 순차 및 반복
아리운에 Laravel 응용 프로그램 배치

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage