【bzoj2282】[Sdoi2011]消防

2015.01.28 16:28 Wed | 8次阅读 | 旧日oi | 固定链接 | 源码

Description

某个国家有n个城市,这n个城市中任意两个都连通且有唯一一条路径,每条连通两个城市的道路的长度为zi(zi<=1000)。
这个国家的人对火焰有超越宇宙的热情,所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍(大量的消防经费开销)可是却又无可奈何(总统竞选的国民支持率),所以只能想尽方法提高消防能力。
现在这个国家的经费足以在一条边长度和不超过s的路径(两端都是城市)上建立消防枢纽,为了尽量提高枢纽的利用率,要求其他所有城市到这条路径的距离的最大值最小。
你受命监管这个项目,你当然需要知道应该把枢纽建立在什么位置上。

Input

输入包含n行:
第1行,两个正整数n和s,中间用一个空格隔开。其中n为城市的个数,s为路径长度的上界。设结点编号以此为1,2,……,n。
从第2行到第n行,每行给出3个用空格隔开的正整数,依次表示每一条边的两个端点编号和长度。例如,“2 4 7”表示连接结点2与4的边的长度为7。

Output

输出包含一个非负整数,即所有城市到选择的路径的最大值,当然这个最大值必须是所有方案中最小的。

Sample Input

【样例输入1】
5 2
1 2 5
2 3 2
2 4 4
2 5 3
【样例输出1】
5
【样例输入2】
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
【样例输出2】
5

题解

这题的数据有问题
网上这题得到题解不多,我写一个吧
首先,遮条枢纽一定在树的直径,也就是树的最长链上,这点应该很好懂吧
那么我们可以找任意一点开始搜,搜到距离最远的点,从这个点再搜,就搜出了直径
接下来二分,二分直径两端可以删除的长度
此时所有的点到直径有一个距离,设其中的最大值为D,那么接下来二分的下界可以设为D
而二分的上界可以设为直径的长度,为什么呢?难道不会存在直径以外的点到直径的距离(此时那个点与直径相连的点不在枢纽上,否则就是下界了)大于枢纽到直径的距离么?当然不会,因为那样的话直径就不会是这条了^ ^

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 300005
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int n,s;
int dis[maxn],dis2[maxn],from[maxn];
bool mark[maxn];
int st[maxn],top;
int q[maxn],f,t;
struct edge{
    int to;
    int next;
    int val;
}e[maxn<<1];
int h[maxn],tp;
void ae(int u,int v,int w)
{
    tp++;
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].val=w;
    h[u]=tp;
}
void bfs(int st)
{
    for(int i=1;i<=n;i++)dis[i]=-1;
    dis[st]=0;
    f=0,t=1;
    q[0]=st;
    while(f!=t)
    {
        int u=q[f++];
        for(int v,i=h[u];e[i].to;i=e[i].next)
        {
            v=e[i].to;
            if(dis[v]!=-1) continue;
            from[v]=u;
            if(mark[v]) dis[v]=dis[u],dis2[v]=dis2[u]+e[i].val;
            else dis[v]=dis[u]+e[i].val;
            q[t++]=v;
        }
    }
}
bool check(int k)
{
    int l=0,r=top;
    while(l<=top&&dis2[st[1]]-dis2[st[l+1]]<=k) l++;
    while(r>0&&dis2[st[r-1]]<=k) r--;
    return dis2[st[l]]-dis2[st[r]]<=s;
}
int main()
{
    cin>>n>>s;
    int u,v,w;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);
        ae(v,u,w);
    }
    int rt=0,x=0,ans;
    bfs(1);for(int i=1;i<=n;i++)if(dis[i]>dis[rt])rt=i;
    bfs(rt);for(int i=1;i<=n;i++)if(dis[i]>dis[x])x=i;
    int r=dis[x],l=0,mid;
    st[++top]=x;while(x!=rt)st[++top]=from[x],x=from[x];
    for(int i=1;i<=top;i++)mark[st[i]]=1;
    bfs(x);
    for(int i=1;i<=n;i++)l=max(l,dis[i]);
    if(s<r)
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}```