問題 D: [Sdoi2011]消防
時間限制: 1 Sec 內存限制: 512 MB
提交: 12 解決: 6
[提交][狀態][討論版]
題目描述
某個國家有n個城市，這n個城市中任意兩個都連通且有唯一一條路徑，每條連通兩個城市的道路的長度為zi(zi<=1000)。
這個國家的人對火焰有超越宇宙的熱情，所以這個國家最興旺的行業是消防業。由于政府對國民的熱情忍無可忍（大量的消防經費開銷）可是卻又無可奈何（總統競選的國民支持率），所以只能想盡方法提高消防能力。
現在這個國家的經費足以在一條邊長度和不超過s的路徑（兩端都是城市）上建立消防樞紐，為了盡量提高樞紐的利用率，要求其他所有城市到這條路徑的距離的最大值最小。
你受命監管這個項目，你當然需要知道應該把樞紐建立在什么位置上。
輸入
輸入包含n行：
第1行，兩個正整數n和s，中間用一個空格隔開。其中n為城市的個數，s為路徑長度的上界。設結點編號以此為1，2，……，n。
從第2行到第n行，每行給出3個用空格隔開的正整數，依次表示每一條邊的兩個端點編號和長度。例如，“2 4 7”表示連接結點2與4的邊的長度為7。
輸出
輸出包含一個非負整數，即所有城市到選擇的路徑的最大值，當然這個最大值必須是所有方案中最小的。
樣例輸入
【樣例輸入1】
5 2
1 2 5
2 3 2
2 4 4
2 5 3
【樣例輸入2】
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
樣例輸出
【樣例輸出1】
5
【樣例輸出2】
5
提示
對于100%的數據，n<=300000，邊長小等于1000。
很容易證得，路徑一定在樹的直徑上。如果路徑拐到了另一條鏈上，明顯不最優。所以求出樹的直徑（兩遍廣搜），再一遍廣搜就可以搞出其它點到直徑的最大距離（只要把直徑上的邊權標為0），把它作為二分的下界，上屆就是樹的直徑了。二分時，只不過要舍棄掉直徑左右兩部分（長度<=mid）即可，最后判斷剩下的長度<=s即可。
現在只要證一下，只要保證直徑上舍棄的長度>=其它點到直徑的距離即可。其實這個沒啥好證的。。想想就明白了。
#pragma GCC optimize("O3")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define N 300005
#define ll long long
using namespace std;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum*f;
}
queue<int> q;
struct road{int v,next,l;}lu[N*2];
int n,s,e,rt1,rt2,top,adj[N],dis[N],vis[N],mark[N],from[N],zhan[N];
void add(int u,int v,int l){lu[++e]=(road){v,adj[u],l};adj[u]=e;}
void bfs(int S)
{memset(dis,-1,sizeof(dis));q.push(S);dis[S]=0;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=adj[x];i;i=lu[i].next){int to=lu[i].v;if(dis[to]==-1){from[to]=x;if(mark[to])dis[to]=dis[x];else dis[to]=dis[x]+lu[i].l;q.push(to);}}}
}
bool check(int x)
{int l=1,r=top;while(zhan[1]-zhan[l+1]<=x&&l<=top)l++;while(zhan[r-1]<=x&&r>=1)r--;return zhan[l]-zhan[r]<=s;
}
int main()
{ n=read();s=read();int x,y,z;for(int i=1;i<n;i++){x=read();y=read();z=read();add(x,y,z);add(y,x,z);}bfs(1);for(int i=1;i<=n;i++)if(dis[i]>dis[rt1])rt1=i;bfs(rt1);for(int i=1;i<=n;i++)if(dis[i]>dis[rt2])rt2=i;int D=dis[rt2];zhan[++top]=dis[rt2];mark[rt2]=1;while(rt2!=rt1){zhan[++top]=dis[from[rt2]];rt2=from[rt2];mark[rt2]=1;}bfs(rt2);int l=0,r=D;for(int i=1;i<=n;i++)l=max(l,dis[i]);if(s<D){while(l<=r){int mid=l+r>>1;if(check(mid))r=mid-1;else l=mid+1;}}printf("%d\n",l);
}
