2019牛客暑期多校训练营（第四场）A meeting（dfs或dp,dp待更新）

示例1：

输入：

4 2
1 2
3 1
3 4
2 4

输出：2

说明：

They can meet at place 1 or 3.

题意：从K个点到达不联通图某个点需要的最短时间，这个最短时间是这K个人最后到达的人所需的时间。

思路：（我觉得官方给的题解挺好理解的就直接复制过来了）

一句话题解：考虑距离最远的两个关键点，设它们的距离为d，d/2上取整即为答案。

必要性：这两个人要碰面，必然要走至少d/2步。

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

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

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

当然对着题面直接dp也是可以做的，但是比较难写。（不会写dp，还需提升能力）。

1、dfs代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int inf=0x3f3f3f3f,maxn=1e5+;

 vector<int>a[maxn];

 int top,n,k,x,y,t,summ,book[maxn];

 void dfs(int p,int q,int step)//p为当前节点，q记录父节点，step记录已走步数

 {

     if(book[p]&&step>summ)//当当前步数大于已标记最大步数和该点上有人时更新最大步数和标记最远端点，以便做第二次寻找最长路的起点

         summ=step,top=p;

     for(int i=; i<a[p].size(); i++)

     {

         if(a[p][i]!=q)

             dfs(a[p][i],p,step+);

     }

 }

 int main()

 {

     scanf("%d%d",&n,&k);

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

     {

         scanf("%d%d",&x,&y);

         a[x].push_back(y),a[y].push_back(x);

     }

     for(int i=; i<k; i++)

     {

         scanf("%d",&t);

         book[t]=;//book数组标记某个点有人

     }

     dfs(t,,);

     dfs(top,,);

     printf("%d\n",summ/);

     return ;

 }

2、dp代码（以后更新）

巴特西

2019牛客暑期多校训练营（第四场）A meeting（dfs或dp,dp待更新）

最新文章

热门文章