首页 > itarticle > uva 1267 – network

uva 1267 – network

admin 11月 11, 2020 0

contents

Problem

有一個 N 節點的樹，要架設服務的 server，必須滿足所有葉節點到最近的 server 距離小於等於 M。一開始會給定一個架好的 server。

求最少的放置個數。

Sample Input

Sample Output

1
2

1 
0

Solution

針對加好的 server，將這個 server 當作 root，將 tree 轉換成 rooted tree，接著使用貪心。

盡可能放置越遠越好，根據 dfs 搜索的順序，查看內部節點 u，其子樹最遠的葉節點深度為何，以及子樹內部距離最近的 server 所在。

共計三種可能

節點 u 逼不得已情況下放置 server
節點 u 無須 server，其子樹的葉節點都已經符合標準
節點 u 無須 server，其子樹的葉節點必須靠另外一個子樹的最近 server 服務。

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int n, m, s, x, y;
int ret = 0;
int dfs(int u, int p, int dep, int &place) {
	int leaf = 0, pp = 0x3f3f3f3f;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == p)
			continue;
		int p;
		int tmp = dfs(v, u, dep + 1, p);
		pp = min(p, pp);
		leaf = max(leaf, tmp);
	}
	place = pp;
	if (leaf - dep + pp - dep <= m)
		leaf = 0;
	if (leaf == dep + m) {
		place = dep;
		ret += (u != s), leaf = 0;
	}
	if (g[u].size() == 1)
		return dep;
	else
		return leaf;
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d", &n, &s, &m);
		for (int i = 0; i <= n; i++)
			g[i].clear();
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			g[x].push_back(y);
			g[y].push_back(x);
		}
		
		ret = 0;
		int foo;
		dfs(s, -1, 0, foo);
		printf("%dn", ret);
	}
	return 0;
}
/*
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
*/