本文主要是介绍hdu 4607 park visit 2013多校联合训练第一场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目的大意是给你一棵树 ，相连节点之间的距离为一，让你找出一个路线访问到k个不同节点 （一条边在这个路径中可以被走多次），问你这样这个路径的距离最小值是多少？
转化之后其实就是要找出数的直径即任意2点间的最大距离，一种方法是任取一个节点做一次广搜找出其最长的子树，然后以该子树的最远的叶子上的节点作为起点再做一次广搜之后得到的最长子树的长度就是树的直径了
对于要访问的点的个数k 小于等于树的直径上的点的数量则答案为k-1
大于的时候 就要考虑怎么走了？肯定走最长路是不够的，但因为最长路的性价比高还是要走最长路，但最长路之外的距离都应该变成2，因为要访问非最长路的点后还得沿原路返回到最长路上来，故答案就是 （k-malen-1)*2+malen = 2*k-malen-2 其中malen为树的直径 ，k-malen-1 是除了数的直径上的点外还需要访问的点个数
#include<cstdio>
#include<vector>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef vector<int>::iterator IntVcIt;
queue<int> que;
vector<vector<int> > tu(100005);
bool vis[100005];
int m=0,n,malen,len[100005];
void read()
{for(int i=1;i<=m;i++)tu[i].clear();scanf("%d%d",&m,&n);for(int i=1;i<m;i++){int a,b;scanf("%d%d",&a,&b);tu[a].push_back(b);tu[b].push_back(a);}
}
int bfs(int start=1)//广搜,默认的起点为1
{memset(vis,0,sizeof(vis));//标记该点有没被访问过memset(len,0,sizeof(len));//初始化从起点到每个点的距离que.push(start);//起点入队int max_start=1;//最长路径的非起点的端点malen=0;//树的直径while(!que.empty()){int temp=que.front();que.pop();for(IntVcIt it=tu[temp].begin();it!=tu[temp].end();++it)if(!vis[*it]){len[*it]=len[temp]+1;if(len[*it]>malen){malen=len[*it];max_start=*it;}que.push(*it);}vis[temp]=1;}return max_start;//返回最长子树的非起点的端点
}void deal()
{bfs(bfs());//2次广搜for(int i=0;i<n;i++){int a;scanf("%d",&a);if(a<=malen+1)printf("%d\n",a-1);elseprintf("%d\n",2*a-malen-2);}
}
int main()
{int T;scanf("%d",&T);while(T--){read();deal();}
}
这篇关于hdu 4607 park visit 2013多校联合训练第一场的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
