第三周 树

猫猫和企鹅

分数 10

全屏浏览

切换布局

作者 姜明欣

单位 河北大学

王国里有 nn 个居住区，它们之间有 n−1 条道路相连，并且保证从每个居住区出发都可以到达任何一个居住区，并且每条道路的长度都为 1。
除 1号居住区外，每个居住区住着一个小企鹅，有一天一只猫猫从 1 号居住区出发，想要去拜访一些小企鹅。可是猫猫非常的懒，它只愿意去距离它在 d 以内的小企鹅们。
猫猫非常的懒，因此希望你告诉他，他可以拜访多少只小企鹅。

输入格式:

第一行两个整数 n,d，意义如题所述。
第二行开始，共 n−1 行，每行两个整数 u,v表示居民区 u 和 v 之间存在道路。

输出格式:

一行一个整数，表示猫猫可以拜访多少只小企鹅。

输入样例:

在这里给出一组输入。例如：

5 1
1 2
1 3
2 4
3 5

输出样例:

在这里给出相应的输出。例如：

2

#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10, M = N * 2;
int e[M], ne[M], h[N], idx;
int depth[N];
int st[N];
int cnt = 0;
int n, d;
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// void dfs(int u, int father, int de)
// {
// //	if(de > d)	return ;
// //		cnt++;// 	for(int i = h[u]; i !=  -1; i = ne[i])
//     {
//         int j = e[i];//         // if(j == father)	continue;
//         if(!st[j] && de < d)
//         {
//        	        st[j] = true;
//        		dfs(j, u, de + 1);
// 			   cnt++;		
// 	    }//     }       // }
void bfs()
{queue<int> q;q.push(1);depth[1] = 0;while(!q.empty()){auto t = q.front();q.pop();for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(!st[j]){st[j] = true;depth[j] = depth[t] + 1;if(depth[j] <= d) cnt++;else    return;q.push(j);}}}
}
int main()
{st[1] = true;cin >> n >> d;memset(h, -1, sizeof(h));for(int i = 1; i < n; i++){int a, b;cin  >> a >> b;add(a, b), add(b, a);}// dfs(1, -1, 0);bfs();
//  int cnt = 0;  for(int i = 2; i <= n; i++)
//        if(depth[i] <= d) cnt++;cout << cnt << endl;
}

会议

分数 15

全屏浏览

切换布局

作者 姜明欣

单位 河北大学

有一个村庄居住着 n 个村民，有 n−1 条路径使得这 n 个村民的家联通，每条路径的长度都为 1。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式:

第一行，一个数 n，表示有 n 个村民。
接下来 n−1 行，每行两个数字 a 和 b，表示村民 a 的家和村民 b 的家之间存在一条路径。

输出格式:

一行输出两个数字 x 和 y。
x 表示村长将会在哪个村民家中举办会议。
y 表示距离之和的最小值。

输入样例:

在这里给出一组输入。例如：

4
1 2
2 3
3 4 

输出样例:

在这里给出相应的输出。例如：

2 4

#include <bits/stdc++.h>
using namespace std;
const int N = 4000;
int g[N][N];
int n;
void floyd()
{for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}}
}
int main()
{memset(g, 0x3f, sizeof(g));cin >> n;for(int i = 1; i < n; i++){int x, y;cin >> x >> y;g[x][y] = g[y][x] = 1;}floyd();int ans = 0x3f3f3f3f;int idx = -1;for(int i = 1; i <= n; i++){int res = 0;for(int j = 1; j <= n; j++){if(i == j)    continue;res += g[i][j];}  if(res < ans){ans = res;idx = i;}}cout << idx << " " << ans;
}