2019牛客暑期多校训练营（第四场）Ameeting

传送门

>传送门<

题意n给城市有n-1条路相连每两个城市之间的道路花费为1有k个人在k个城市问这k个人聚集在同一个城市的最小花费

思路官方给的题解写的挺好理解的

考虑距离最远的两个关键点设它们的距离为dd/2上取整即为答案。

• 必要性这两个人要碰面必然要走至少d/2步。
• 充分性我们取两人路径中和一头距离为d/2上取整的一个点让所有人在这相聚。如 果有一个人在d/2时间内到不了那么它和路径两头中与它远的那一头的距离大于d与 最远的假设矛盾。

找到这样最远的一对点类似找树的直径。可以直接dp也可以采用两遍dfs

从任意一个关键点开始找到离它最远的关键点x再从x开始dfs找到的新的最远点和x形成的就是直径。

当然对着题面直接dp也是可以做的但是比较难写。

Code

#include using namespace std;typedef long long ll;const int MAX_N 1e57;int n, k, s, ans;int vis[MAX_N];vector G[MAX_N];void dfs(int u, int pre, int step){if(vis[u] step, s u;//或者用auto v: G[u]for (int i 0; i > n >> k;for(int i 1; i > u >> v;G[u].push_back(v);G[v].push_back(u);}int x;for(int i 1; i >x, vis[x] 1;dfs(x, 0, 1);dfs(s, 0, 1); //初始step为1就相当于最后ans向上取整了 cout <2;return 0;} View Code

 

转:https://www.cnblogs.com/wizarderror/p/11269544.html

【文章原创作者：大丰网站制作公司 http://www.1234xp.com/dafeng.html 提供，感恩】