SDOI2011的Dayx第2題

題意：

　　在樹中找到一條權值和不超過S的鏈（為什么是鏈呢，因為題目中提到“使得路徑的兩端都是城市”，如果不是鏈那不就不止兩端了嗎——怎么這么機智的感覺...），使得不在鏈上的點與這條鏈的距離最大值最小。

SOL：

　　最大值最小！這不是二分的節奏么？然而hzw學長說二分更直觀我卻一點都沒有體會到...

　　這道題的關鍵是猜想（貌似還挺好想）并證明（貌似一直都是可有可無的東西，不過還挺好證的），路徑一定在直徑上，那么我們先兩遍*FS找到直徑，用一個隊列維護鏈上的路徑，以及預處理出直徑上的點其子樹中距離最遠的點的距離，再維護路徑兩頭距離直徑的兩端的距離即可，答案即這三者的最大值。

　　總感覺應該挺快的吧但是居然比他們二分答案的慢了幾倍（A得窩囊），我也就是用了一個set而已（方便取出與刪除然而我覺得可以再優化不用這個set...

　　關于證明：（自己口胡的證明，極其不嚴謹

　　　　證明還是非常好證的（也就自己yy），我們假設一條直徑，假設最優的鏈不在這條直徑上——我們可以把這條鏈看作一個點，那么可以證明它的最遠點一定是直徑的兩個端點之一（否則樹的直徑就可以更長），那么顯然這條鏈是包含直徑的一部分的，再證全部包含，只要在部分包含的基礎上對延伸進行討論，就得證了吧...（感覺對了就好了不過是給自己a掉多找一個正當理由...）

CODE：

代碼實現不是很難，然而我RE幾次方了把DFS改成BFS又把自帶queue改成手工隊列——結果小細節錯誤百出...

1 /*========================================================================== 2 # Last modified: 2016-02-12 3 # Filename: 2016trainning1 t1.cpp 4 # Description: 5 ==========================================================================*/ 6 #define me AcrossTheSky 7 #include <cstdio> 8 #include <cmath> 9 #include <ctime> 10 #include <string> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 16 #include <set> 17 #include <map> 18 #include <stack> 19 #include <queue> 20 #include <vector> 21 #define lowbit(x) (x)&(-x) 22 #define INF 1000000000 23 #define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++) 24 #define FORP(i,a,b) for(int i=(a);i<=(b);i++) 25 #define FORM(i,a,b) for(int i=(a);i>=(b);i--) 26 #define ls(a,b) (((a)+(b)) << 1) 27 #define rs(a,b) (((a)+(b)) >> 1) 28 #define check(ch) (ch>='0'&&ch<='9') 29 #define maxn 300001 30 using namespace std; 31 typedef long long ll; 32 typedef unsigned long long ull; 33 int ans=INF; 34 void read(int &t){ 35 int ch; 36 for(ch=getchar( );!check(ch);ch=getchar( )); 37 t=ch-'0'; 38 for(ch=getchar( );check(ch);ch=getchar( ))t*=10,t+=ch-'0'; 39 } 40 /*==================split line==================*/ 41 int n,s,sume=0,maxx; 42 struct Edge{ 43 int to,len; 44 }e[maxn*2]; 45 struct cmp{ 46 bool operator()(const int &x,const int &y) const{ 47 return x>y; 48 } 49 }; 50 int first[maxn],next[maxn*2],nextn[maxn],dis[maxn],temp[2],f[maxn],pre[maxn]; 51 int q[maxn*2]; 52 bool vis[maxn]; 53 set<int,cmp> b; 54 void addedge(int x,int y,int len){ 55 sume++; e[sume].to=y; e[sume].len=len; 56 next[sume]=first[x]; first[x]=sume; 57 } 58 void bfs(int node,int d){ 59 memset(q,0,sizeof(q)); 60 int front=1,tail=1; dis[node]=0; 61 q[front]=node; vis[node]=true; 62 while (front<=tail){ 63 int x=q[front]; 64 front++; 65 if (dis[x]>maxx) maxx=dis[x],temp[d]=x; 66 for (int i=first[x];i!=-1;i=next[i]) 67 if (!vis[e[i].to]){ 68 pre[e[i].to]=x; 69 dis[e[i].to]=dis[x]+e[i].len; 70 tail++; q[tail]=e[i].to; vis[e[i].to]=true; 71 } 72 } 73 } 74 void bfs1(int node,int root){ 75 memset(q,0,sizeof(q)); 76 int front=1,tail=1; q[front]=node; 77 while (front<=tail){ 78 int x=q[front]; front++; vis[x]=true; 79 f[root]=max(f[root],dis[x]-dis[root]); 80 for (int i=first[x];i!=-1;i=next[i]) 81 if (e[i].to!=nextn[node] && !vis[e[i].to]){ 82 tail++; q[tail]=e[i].to; 83 } 84 } 85 } 86 int main(){ 87 read(n); read(s); 88 FORP(i,1,n) first[i]=-1; 89 FORP(i,1,n-1) { 90 int x,y,l; 91 read(x); read(y); read(l); 92 addedge(x,y,l); addedge(y,x,l); 93 } 94 maxx=0; bfs(1,0); 95 memset(vis,false,sizeof(vis)); 96 maxx=0; bfs(temp[0],1); 97 int L=temp[1],R=temp[0]; 98 memset(vis,false,sizeof(vis)); 99 for (int i=L;i!=R;i=pre[i]) nextn[pre[i]]=i; 100 L=temp[0],R=temp[1]; 101 for (int i=L;i!=R;i=nextn[i]) { vis[i]=true; bfs1(i,i); } 102 vis[R]=true; bfs1(R,R); 103 int llen=0,rlen=maxx,head=L,tail=L,len=0; 104 105 while (true){ 106 if (head==R) break; 107 if (dis[nextn[head]]<s) { 108 len=dis[nextn[head]]; 109 head=nextn[head]; 110 b.insert(f[head]); 111 rlen=maxx-dis[head]; 112 continue; 113 } 114 break; 115 } 116 117 int t=max(rlen,max(llen,*b.begin())); 118 if (t<ans) ans=t; 119 while (head!=R){ 120 len=dis[nextn[head]]; 121 head=nextn[head]; 122 rlen=maxx-dis[head]; 123 while(len-dis[tail]>s){ 124 b.erase(f[tail]); tail=nextn[tail]; llen=dis[tail]; 125 } 126 t=max(rlen,max(llen,*b.begin())); 127 if (t<ans) ans=t; 128 } 129 printf("%d",ans); 130 } View Code

?

轉載于:https://www.cnblogs.com/YCuangWhen/p/5188165.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ 2282 树的直径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。