题目：http://acm.hdu.edu.cn/showproblem.php?pid=4607
题意就是给你一颗顶点个数为N的树，每相连的两个点之间的距离都是1，然后要游历其中的K个，这K个是任意的，然后要求的是走的距离的最小值，
这题实际上感觉还是挺水的吧，距离的最小值，有两种情况，第一种就是当K小于或等于树中最长链的结点数t的时候， 最短距离就是K -1，否则的话就是t - 1 + 2 * (K - t);这个很好想，就是以最长链为主游历其他的点然后返回，这样就多走了一个距离，加上就是最终结果。
然后求树的最长链的时候，用两次广搜，第一次以任意点位起点，找到最后出栈的那个点a，然后再以最后出栈的那个点为起点再广搜一次，a到最后出栈的那个点之间的结点的个数就是要求的数的最长链的结点数。
代码：
#include<cstdio> #include<cstring> #define MAXN 100010 struct Edge{ int to, next; }; Edge edges[2*MAXN]; int head[MAXN]; int que[MAXN], dist[MAXN]; int cnt, N; void add_edge(int a, int b) { edges[cnt].to = b; edges[cnt].next = head[a]; head[a] = cnt ++; } int BFS(int s) { int front = 0, rear = 0; memset(dist, -1, sizeof(dist)); dist[s] = 0; int record; que[front] = s; rear ++; while(front < rear) { int hd = que[front]; record = hd; front ++; for(int i = head[hd]; i != -1; i = edges[i].next) { int t = edges[i].to; if(dist[t] == -1) { dist[t] = dist[hd] + 1; que[rear] = t; rear ++; } } } return record; } int main() { freopen("hdu4607.txt", "r", stdin); int T, M, a, b, m; scanf("%d", &T); while(T --) { memset(head, -1, sizeof(head)); scanf("%d%d", &N, &M); cnt = 0; for(int i = 1; i < N; ++ i) { scanf("%d%d", &a, &b); add_edge(a, b); add_edge(b, a); } int t = BFS(1); t = BFS(t); t = dist[t] + 1; while(M --) { scanf("%d", &m); if(m <= t) { printf("%d\n", m - 1); } else { printf("%d\n", t -1 + 2 * (m - t)); } } } return 0; } |