問題 D: [Sdoi2011]消防
時間限制: 1 Sec 內(nèi)存限制: 512 MB
提交: 12 解決: 6
[提交][狀態(tài)][討論版]
題目描述
某個國家有n個城市，這n個城市中任意兩個都連通且有唯一一條路徑，每條連通兩個城市的道路的長度為zi(zi<=1000)。
這個國家的人對火焰有超越宇宙的熱情，所以這個國家最興旺的行業(yè)是消防業(yè)。由于政府對國民的熱情忍無可忍（大量的消防經(jīng)費開銷）可是卻又無可奈何（總統(tǒng)競選的國民支持率），所以只能想盡方法提高消防能力。
現(xiàn)在這個國家的經(jīng)費足以在一條邊長度和不超過s的路徑（兩端都是城市）上建立消防樞紐，為了盡量提高樞紐的利用率，要求其他所有城市到這條路徑的距離的最大值最小。
你受命監(jiān)管這個項目，你當然需要知道應(yīng)該把樞紐建立在什么位置上。
輸入
輸入包含n行：
第1行，兩個正整數(shù)n和s，中間用一個空格隔開。其中n為城市的個數(shù)，s為路徑長度的上界。設(shè)結(jié)點編號以此為1，2，……，n。
從第2行到第n行，每行給出3個用空格隔開的正整數(shù)，依次表示每一條邊的兩個端點編號和長度。例如，“2 4 7”表示連接結(jié)點2與4的邊的長度為7。
輸出
輸出包含一個非負整數(shù)，即所有城市到選擇的路徑的最大值，當然這個最大值必須是所有方案中最小的。

樣例輸入
【樣例輸入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%的數(shù)據(jù)，n<=300000，邊長小等于1000。

很容易證得，路徑一定在樹的直徑上。如果路徑拐到了另一條鏈上，明顯不最優(yōu)。所以求出樹的直徑（兩遍廣搜），再一遍廣搜就可以搞出其它點到直徑的最大距離（只要把直徑上的邊權(quán)標為0），把它作為二分的下界，上屆就是樹的直徑了。二分時，只不過要舍棄掉直徑左右兩部分（長度<=mid）即可，最后判斷剩下的長度<=s即可。
現(xiàn)在只要證一下，只要保證直徑上舍棄的長度>=其它點到直徑的距離即可。其實這個沒啥好證的。。想想就明白了。

#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); }

轉(zhuǎn)載于:https://www.cnblogs.com/QTY2001/p/7632632.html

總結(jié)

以上是生活随笔為你收集整理的二分+树的直径 [Sdoi2011]消防的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。