首页 > 代码库 > ZOJ 3820 Building Fire Stations 求中点+树的直径+BFS
ZOJ 3820 Building Fire Stations 求中点+树的直径+BFS
题意：给一棵树，要求找出两个点，使得所有点到这两个点中距离与自己较近的一个点的距离的最大值（所有点的结果取最大的值，即最远距离）最小。 意思应该都能明白。
解法：考虑将这棵树摆直如下：
那么我们可以把最中间的那条直径边删掉，然后在分成的两颗子树内求一个直径中心点，那么这两个点就可以作为答案。 反正当时就觉得这样是正确的， 但是不能证明。
于是，几个bfs就可以搞定了。
当时写TLE了，原因是存要删的边我用了map<pair<int,int>,int>， 后来改掉就不T了，map这种东西还是尽量少用。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <queue>using namespace std;#define N 200007int vis[N],fa[N];int maxi,maxtag;struct node{ int dis,u;};vector<int> G[N];int U,V;void bfs(int S){ node now; now.u = S; now.dis = 0; maxi = 0, maxtag = S; queue<node> que; fa[S] = -1; memset(vis,0,sizeof(vis)); que.push(now); vis[S] = 1; while(!que.empty()) { node tmp = que.front(); que.pop(); int dis = tmp.dis; int u = tmp.u; if(dis > maxi) //最远的点 maxi = dis, maxtag = u; for(int i=0;i<G[u].size();i++) { int v = G[u][i]; if(vis[v]) continue; if((u == U && v == V)||(u == V && v == U)) continue; now.dis = dis+1; now.u = v; fa[v] = u; vis[v] = 1; que.push(now); } }}int Smaxi,Smaxtag;int Emaxi,Emaxtag;void findcenter(int S,int& ma,int& tag){ ma = 0, tag = S; bfs(S); int NS = maxtag; bfs(NS); int NE = maxtag; int cnt = (maxi+1)/2; int nc = 0; int i = NE; while(1) { nc++; if(nc > cnt) { tag = i; break; } i = fa[i]; } bfs(tag); ma = maxi;}int main(){ int t,n,i,u,v; scanf("%d",&t); while(t--) { U = V = -1; scanf("%d",&n); for(i=0;i<=n;i++) G[i].clear(); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } bfs(1); int S = maxtag; bfs(S); int E = maxtag; int cnt = (maxi+1)/2; int nc = 0; i = E; while(1) { nc++; if(nc >= cnt) { U = i, V = fa[i]; break; } i = fa[i]; } findcenter(S,Smaxi,Smaxtag); findcenter(E,Emaxi,Emaxtag); printf("%d %d %d\n",max(Smaxi,Emaxi),Smaxtag,Emaxtag); } return 0;}
ZOJ 3820 Building Fire Stations 求中点+树的直径+BFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。