牛客多校第四场 A
- 题意：
- 给出一个无向图，每条连通的点的距离都为1，
- 给出k个点，每个点上有一个人，每个人的步行速度是1，问最短需要多少时间，所有人能走到一个点上。
- 题解：
- 很好就能想出来，最短时间 = 相离最远的俩个人的距离/2，向上取整。
- 如何找这个最远的距离，用俩次bfs，这里不得不说真的很巧妙，
- 随意找一个人所在的点，dfs，找距离这个点最远的另一个人，
- 然后以找到的最远的那个人，再次bfs，和上面的bfs一样，找最远的第三个人。
- 那么答案就是第二遍bfs的距离，
- 不明白的可以在一条直线上画一下，就明白了。
- 代码：
#include <bits/stdc++.h> using namespace std; int n,k,p,ans = 0; int a[100010],flag[100010],sign[100010]; vector<int> v[100010]; void dfs(int x,int len) { a[x] = len; if(sign[x] == 1 && a[x] > ans){ ans = a[x]; p = x; } for(int i=0;i<v[x].size();i++) { if(!flag[v[x][i]]){ flag[v[x][i]] = 1; dfs(v[x][i],len+1); } } return ; } int main() { int x,y; scanf("%d%d",&n,&k); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } for(int i=1;i<=k;i++) { scanf("%d",&x); sign[x] = 1; } dfs(x,0); ans = 0; memset(flag,0,sizeof(flag)); dfs(p,0); cout<<(ans+1)/2<<endl; return 0; }
文远知行公司福利 465人发布