本文主要是介绍zoj3820(树的直径的应用)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：在一颗树上找两个点，使得所有点到选择与其更近的一个点的距离的最大值最小。思路：如果是选择一个点的话，那么点就是直径的中点。现在考虑两个点的情况，先求树的直径，再把直径最中间的边去掉，再求剩下的两个子树中直径的中点。
代码如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>#define inf 0x3f3f3f3f
#define N 200005
using namespace std;
int head[N],tot;
struct node
{int v,next;
}edge[N<<1];
void addedge(int u,int v)
{edge[tot].next = head[u];edge[tot].v = v;head[u] = tot++;
}
int step[N],vis[N],pre[N];
int x,y;
int bfs(int u,int& cnt)
{memset(vis,0,sizeof(vis));queue<int> q;q.push(u);step[u] = 0;vis[u] = 1 ;pre[u] = -1;int now;while(!q.empty()){now = q.front();q.pop();for(int i = head[now]; i != -1; i = edge[i].next){int v = edge[i].v;if(vis[v]) continue;if(now == x && v == y) continue;if(now == y && v == x) continue;step[v] = step[now] + 1;//if(step[v] > ans) ans = step[v];cnt = max(cnt,step[v]);vis[v] = 1;pre[v] = now;q.push(v);}}return now;
}
int find_node(int u,int dist)
{int cnt = 1;while(1){if(cnt == dist/2) break;u = pre[u];cnt++;}return u;
}
int main()
{int t;scanf("%d",&t);while(t--){memset(head,-1,sizeof(head));tot = 0; x = y = inf;int n;scanf("%d",&n);int i;for(i = 1; i < n; i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}int st = bfs(1,i);int ed = bfs(st,i);//cout<<st<<" "<<ed<<endl;//for(i = 1; i <= n; i++)// cout<<step[i]<<" ";cout<<endl;//cout<<step[ed]<<endl;x = find_node(ed,step[ed]+2);y = pre[x];//找到要去除的边x - y//cout<<x<<" "<<y<<endl;int st1 = bfs(st,i);int ed1 = bfs(st1,i);int ans1 = find_node(ed1,step[ed1]+2);int st2 = bfs(ed,i);int ed2 = bfs(st2,i);int ans2 = find_node(ed2,step[ed2]+2);int ans = 0,temp = 0;bfs(ans1,temp); ans = max(ans,temp);temp = 0;bfs(ans2,temp); ans = max(ans,temp);printf("%d %d %d\n",ans, ans1,ans2);}return 0;
}
这篇关于zoj3820(树的直径的应用)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
