1267 - Network (贪心)

By | 12月16日
Advertisement

Consider a tree network withnnodes where the internal nodes correspond to servers and the terminal nodes correspond to clients. The nodes are numbered from 1 ton. Among the servers, there is an original serverSwhich provides VOD (Video On Demand) service. To ensure the quality of service for the clients, the distance from each client to the VOD serverSshould not exceed a certain valuek. The distance from a nodeuto a nodevin the tree is defined to be the number of edges on the path fromutov. If there is a nonempty subsetCof clients such that the distance from eachuinCtoSis greater thank, then replicas of the VOD system have to be placed in some servers so that the distance from each client to the nearest VOD server (the original VOD system or its replica) iskor less.

Given a tree network, a serverSwhich has VOD system, and a positive integerk, find the minimum number of replicas necessary so that each client is within distancekfrom the nearest server which has the original VOD system or its replica.

For example, consider the following tree network.

1267 - Network (贪心)

In the above tree, the set of clients is {1, 6, 7, 8, 9, 10, 11, 13}, the set of servers is {2, 3, 4, 5, 12, 14}, and the original VOD server is located at node 12.

Fork= 2, the quality of service is not guaranteed with one VOD server at node 12 because the clients in {6, 7, 8, 9, 10} are away from VOD server at distance>k. Therefore, we need one or more replicas. When one replica is placed at node 4, the distance from each client to the nearest server of {12, 4} is less than or equal to 2. The minimum number of the needed replicas is one for this example.

Input

Your program is to read the input from standard input. The input consists ofTtest cases. The number of test cases (T) is given in the first line of the input. The first line of each test case contains an integern(31267 - Network (贪心)
n1267 - Network (贪心)
1, 000)which is the number of nodes of the tree network. The next line contains two integerss(11267 - Network (贪心)
s1267 - Network (贪心)
n)andk(k1267 - Network (贪心)
1)wheresis the VOD server andkis the distance value for ensuring the quality of service. In the followingn - 1lines, each line contains a pair of nodes which represent an edge of the tree network.

Output

Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer that is the minimum number of the needed replicas.

Sample Input

2 14
12 2
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11
14
3 4
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11

Sample Output

1
0

题意:给定一个图,求最少放置几个服务器使得全部覆盖。

思路:贪心,从叶子节点,找他的k级节点去放置是最佳情况。

代码:

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int N = 1005;

int T, n, s, k, vis[N], f[N], vi[N];
vector<int> g[N], node[N];

void dfs(int s, int d) {
    if (d <= k)
    vis[s] = 1;
    vi[s] = 1;
    if(g[s].size() == 1) node[d].push_back(s);
    for (int i = 0; i < g[s].size(); i ++) {
    if (vi[g[s][i]] == 0) {
        f[g[s][i]] = s;
        dfs(g[s][i], d + 1);
    }
    }
}

void dfs2(int s, int d) {
    if (d > k) return;
    vis[s] = 1;
    vi[s] = 1;
    for (int i = 0; i < g[s].size(); i ++) {
    if (vi[g[s][i]] == 0)
        dfs2(g[s][i], d + 1);
    }
}

void init() {
    memset(f, 0, sizeof(f));
    memset(vi, 0, sizeof(vi));
    memset(vis, 0, sizeof(vis));
    memset(g, 0, sizeof(g));
    memset(node, 0, sizeof(node));
    scanf("%d%d%d", &n, &s, &k);
    int a, b;
    for (int i = 0; i < n - 1; i ++) {
    scanf("%d%d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
    }
    dfs(s, 0);
}

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

int main() {
    scanf("%d", &T);
    while (T--) {
    init();
    printf("%d\n", solve());
    }
    return 0;
}

Similar Posts:

  • UVa 1267 Network (DFS&amp;贪心)

    1267 - Network Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=3708 Consider a tree network with n nodes where the internal nodes correspond to servers a

  • UVa 1267 Network (DFS&amp;amp;贪心)

    1267 - Network Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=3708 Consider a tree network with n nodes where the internal nodes correspond to servers a

  • UVA 1456 Cellular Network(贪心,DP)

    题意: (摘自LRJ<训练指南>)手机在蜂窝网络中的定位是一个基本问题.假设蜂窝网络已经得知手机处于c1, c2,-,cn这些区域中的一个,最简单的方法是同时在这些区域中寻找手机.但这样做很浪费带宽.由于蜂窝网络中可以得知手机在这不同区域中的概率,因此一个折中的方法就是把这些区域分成w组,然后依次访问.比如,已知手机可能位于5个区域中,概率分别为0.3.0.05.0.1.0.3和0.25,w=2,则一种方法是先同时访问{c1,c2,c3},再同时访问{c4,c5},访问区域数的数学期望为3*(

  • 【索引】General Problem Solving Techniques:Examples

    AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) Chapter 1. Algorithm Design::General Problem Solving Techniques:Examples 11292 - Dragon of Loowater 11729 - Commando War 11300 - Spreading the Wealth 1388 - Graveyard 10881 - Piotr's

  • [置顶] 算法竞赛入门经典(训练指南)(刘汝佳 陈锋)个人训练计划

    2013 ACM训练计划 主体计划是:刷算法竞赛入门经典(训练指南这本书) 5月份:第一章:算法设计基础 6月份:第三章:实用数据结构 7月份:第五章:图论算法与模型 8月份:第六章:更多算法专题 9月份:第二章:数学基础 9月份:第四章:几何问题. 我的ACM生涯 上半年邀请赛: 南京赛区 南京理工大学邀请赛(现场赛)4月底 广东省赛 华南农业大学(现场赛)5月12日 长沙赛区 湖南大学邀请赛(现场赛)5月19日 长春赛区 通化师范大学(现场赛) 5.18-5.19 杭州赛区 浙江工业大学邀请

  • POJ 3659 Cell Phone Network【最小支配集 dp &amp;&amp; 贪心】

    Cell Phone Network Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6231   Accepted: 2230 Description Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires hi

  • DP + 概率 + 贪心 UVA 1456 Cellular Network

    题目传送门 题意:(摘自LRJ<训练指南>) 手机在蜂窝网络中的定位是一个基本问题.假设蜂窝网络已经得知手机处于c1, c2,-,cn这些区域中的一个,最简单的方法是同时在这些区域中寻找手机.但这样做很浪费带宽.由于蜂窝网络中可以得知手机在这不同区域中的概率,因此一个折中的方法就是把这些区域分成w组,然后依次访问.比如,已知手机可能位于5个区域中,概率分别为0.3.0.05.0.1.0.3和0.25,w=2,则一种方法是先同时访问{c1,c2,c3},再同时访问{c4,c5},访问区域数的数学

  • Deep Learning 学习随记(五)Deep network 深度网络

    这一个多周忙别的事去了,忙完了,接着看讲义~ 这章讲的是深度网络(Deep Network).前面讲了自学习网络,通过稀疏自编码和一个logistic回归或者softmax回归连接,显然是3层的.而这章则要讲深度(多层)网络的优势. Deep Network: 为什么要使用深度网络呢?使用深度网络最主要的优势在于,它能以简洁的方式来表达比浅层网络大得多的函数集合.正式点说,可以找到一些函数,它们能够用k层网络简洁的表达出来(这里的简洁指的是使用隐层单元的数目与输入单元数目是多项式关系),但是对一

  • Network Attack

    Network Attack Nicola regularly inspects the local networks for security issues. He uses a smart and aggressive program which takes control of computers on the network. This program attacks all connected computers simultaneously, then uses the captur

  • hdoj 5463 Clarke and minecraft 【简单贪心】

    Clarke and minecraft Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 534 Accepted Submission(s): 276 Problem Description Clarke is a patient with multiple personality disorder. One day, Clarke tur

Tags: