https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=283&page=show_problem&problem=1903

題意：在一個(gè)樹(shù)狀的網(wǎng)絡(luò)中，提供VOD服務(wù)，葉子節(jié)點(diǎn)是客戶(hù)端，其他是服務(wù)器，要減少網(wǎng)絡(luò)延遲，所以要在其他的服務(wù)器也安裝同樣的服務(wù)，使得每臺(tái)客戶(hù)端到最近服務(wù)器的距離不超過(guò)k，求最少安裝服務(wù)的服務(wù)器。

思路：一個(gè)關(guān)鍵點(diǎn)是選擇u節(jié)點(diǎn)的k級(jí)祖先是最優(yōu)的，因?yàn)楦采w的范圍最廣，所以我們構(gòu)造出一顆有根樹(shù)，從下往上遍歷葉子節(jié)點(diǎn)，看是否被覆蓋，沒(méi)有則在k級(jí)祖先安裝服務(wù)。

?

    #include <iostream>

#include <vector>

using namespace std;



#define MAXN 1010

vector<int> link[MAXN];//存樹(shù)

vector<int> node[MAXN];//存第i層節(jié)點(diǎn)



int n, s, k, father[MAXN];

bool used[MAXN];



void dfs(int u, int fa, int d)//無(wú)根樹(shù)轉(zhuǎn)有根樹(shù)，計(jì)算father數(shù)組，根據(jù)深度插入node表

{

	father[u] = fa;

	int size = link[u].size();

	if (size == 1 && d > k) node[d].push_back(u);//一個(gè)

	for (int i = 0; i < size; i++)				 //多個(gè)

	{

		if (link[u][i] != fa) dfs(link[u][i], u, d + 1);

	}

}



void dfs2(int u, int fa, int d)

{

	used[u] = true;

	for (int i = 0; i < link[u].size(); i++)

	{

		if (link[u][i] != fa && d < k) dfs2(link[u][i], u, d + 1);

	}

}



int solve()

{

	int ans = 0;

	memset(used, 0, sizeof(used));

	for (int d = n - 1; d > k; d--)

	{

		for (int i = 0; i < node[d].size(); i++)

		{

			int u = node[d][i];

			if (!used[u]) //未被覆蓋

			{

				int tmp = u;

				for (int j = 0; j < k; j++) tmp = father[tmp];//tmp是u的k級(jí)祖先

				dfs2(tmp, -1 ,0);

				ans ++;

			}

		}

	}

	return ans;

}



int main()

{

	int T;

	cin>>T;

	while (T--)

	{

		cin>>n>>s>>k;

		for (int i = 1; i <= n; i++) 

		{

			link[i].clear();

			node[i].clear();

		}

		for (i = 0; i < n - 1; i++)

		{

			int a, b;

			cin>>a>>b;

			link[a].push_back(b);

			link[b].push_back(a);

		}

		dfs(s, -1, 0);//節(jié)點(diǎn)，父節(jié)點(diǎn)，深度

		printf("%d\n", solve());

	}

	return 0;

}
  

?

?

2007LA 3902 網(wǎng)絡(luò)(樹(shù)+貪心)