首页 > 代码库 > zoj3820 树的直径+二分
zoj3820 树的直径+二分
这题是个遗憾 ！！！！！当时一直不敢相信两个站一定在直径上，赛后想想自己真的是脑袋抽风， 如果其中一个站不在直径上就反向的说明了这条不是直径。可以很明白我们可以肯定的是有一个点一定在直径上假如另外一个点不在直径上，那么他在分支上，那么可以知道直径上的某点一定大于这个分支的最远点，显然放在这个分支上是不合适的。好现在我们知道了者两个点一定在直径上，二分可能最小的距离，
求直径 先从一个点 bfs到离他最远的点a ，然后从a bfs 到离他 最远的点b ,然后 记录路径，就得到了 ab为直径上的树，那么现在将每个直径上的点进行bfs得到了算以他为根的分支最远点（不算直径），然后每次二分后，从直径的两段朝中间走，知道走到二分的答案，然后判断可不可行， 我i好渣,当时脑袋真的被抽风了！
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <vector>#include <queue>using namespace std;const int maxn = 200005;vector<int> F[maxn],rdio;int n;int per[maxn],dist[maxn];bool use[maxn];int bfs(int s,int &ma){ ma=-1; queue<int> Q; use[s]=true; int loc; dist[s]=0; per[s]=-1; Q.push(s); while(!Q.empty()){ int t=Q.front(); Q.pop(); int siz=F[t].size(); if(dist[t]>ma){ ma=dist[t]; loc=t; } for(int i=0; i<siz ; ++i){ int to = F[t][i]; if(use[to]==true)continue; dist[to]=dist[t]+1; use[to]=true; per[to]=t; Q.push(to); } } return loc;}int Len;int madist[maxn];bool jud(int dist, int &x, int &y){ x=0; y=Len-1; int d1=madist[0]; if(d1>dist) return false; while(true){ if(x+1==y) break; int d = max( d1+1,madist[x+1]); if( d > dist ) break ; d1=d; x++; } d1=madist[y]; if(d1>dist) return false; while(true){ if(y-1==x)break; int d= max(d1+1,madist[y-1]); if(d>dist) break; d1=d; y--; } for(int i=x+1; i<y; ++i){ int d = min(madist[i]+abs(i-x),madist[i]+abs(i-y)); if(d>dist) return false; } return true;}int main(){ int cas; scanf("%d",&cas); while(cas--){ scanf("%d",&n); rdio.clear(); for(int i=0; i<=n; ++i ) F[i].clear(); for(int i=1; i<n; ++i){ int a,b; scanf("%d%d",&a,&b); F[a].push_back(b); F[b].push_back(a); } memset(use,false,sizeof(use)); int ttt; int st=bfs(1,ttt); memset(use,false,sizeof(use)); int ed=bfs(st,ttt); memset(use,false,sizeof(use)); for(int i = ed; i!=-1; i=per[i]){ rdio.push_back(i); use[i]=true; } for(int i=0; i<int(rdio.size()) ; ++i) bfs(rdio[i],madist[i]); Len=rdio.size(); int L=0,R=n; int x,y,anx,any; while( L<R ){ int mid=(L+R)/2; if(jud(mid,x,y)==true){ R=mid; anx=x; any=y; } else L=mid+1; } printf("%d %d %d\n",R,rdio[anx],rdio[any]); } return 0;}
zoj3820 树的直径+二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。