[牛客暑期多校第四场][思维]A-meeting

发布于 2019-07-29  727 次阅读


https://ac.nowcoder.com/acm/contest/884/A

这个题我在最后一小时开始看的 说实话 我的思路有一定的正确性 不过当时感觉好累 都没有写的动力了

题意很简单 给N M N个点 M个关键点
之后给N-1条边 就是将所有的点连接成一个图 然后M个点上有人 他们要聚到一起 求一个关键点 这个关键点要求所有人到达的最小值(输出最大的那个)
感觉题意好像没说明白啊。。。
解题思路 这个题要去找的就是最远的两个关键点之间的距离/2向上取整 这个值就是所求的答案 如何找这个关键点 首先建图 之后开始从编号为1的点扫 扫到第一个关键点(不一定是端点之一) 开始dfs 求出所有点到这个点的距离
之后找到离这个点最远的那个点 (一定是个端点) 再进行一次DFS 然后就可以找到另外一个端点了 代码参考咖啡鸡的代码 不得不说 真的强

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 505050;
vector<int> ve[maxn];
int n, m;
int dis[maxn];
int vis[maxn];
int pos, ans;

void dfs(int u, int fa) {
	for (auto v : ve[u]) {
		if (v == fa) continue;
		dis[v] = dis[u] + 1;
		dfs(v, u);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {//建图
		int u, v;
		cin >> u >> v;
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	for (int i = 1; i <= m; i++) {//输入关键点 vis=1
		int u;
		cin >> u;
		vis[u] = 1;
	}
	for (int i = 1; i <= n; i++) {//从第一个点开始找关键点 找到第一个关键点(不一定是端点) 开始dfs
		if (vis[i]) {
			dis[i] = 0;//到自身=0
			pos = i;//记录该点
			dfs(i, 0);
			break;
		}
	}
	for (int i = 1; i <= n; i++) {//再扫一遍所有点 寻找离记录的点最远的关键点(端点一号)
		if (vis[i] && dis[pos] < dis[i]) {
			pos = i;
		}
	}
	dis[pos] = 0;//最远关键点到自身=0
	dfs(pos, 0);//再搜一遍
	for (int i = 1; i <= n; i++) {
		if (vis[i]) ans = max(ans, (dis[i] + 1) / 2);//最远的那个 就是另一个端点
	}
	cout << ans << endl;
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。