Bzoj 2282: [Sdoi2011]消防(二分答案)

2282: [Sdoi2011]消防

Time Limit: 10 Sec Memory Limit: 512 MB

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

【样例输入2】

8 6

1 3 2

2 3 2

3 4 6

4 5 3

4 6 4

4 7 2

7 8 3

Sample Output

【样例输出1】

5

【样例输出2】

5

HINT

对于100%的数据，n<=300000，边长小等于1000。

Source

stage 2 day1

/*

在直径上二分乱搞.

一开始猜结论感觉直径的中点一定被覆盖.

然后写了一发贪心,w了 不知道为啥orz....

并不会证明.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define MAXN 300001

using namespace std;

int n,m,ans,fa[MAXN],s[MAXN],l,r,cut,dis[MAXN],sum[MAXN],tot,w[MAXN],head[MAXN],S,maxt,max1,maxt2,maxx;

struct edge{int v,next,x;}e[MAXN*2];

queue<int>q;

bool b[MAXN];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,int x)

{

    e[++cut].v=v;e[cut].x=x;e[cut].next=head[u];head[u]=cut;

}

void bfs1()

{

    q.push(1);

    for(int i=1;i<=n;i++) dis[i]=-1;dis[1]=0;

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]==-1)

            {

                dis[v]=dis[u]+e[i].x,q.push(v);

                if(dis[v]>max1) max1=dis[v],maxt=v;

            }

        }

    }

}

void bfs2()

{

    q.push(maxt);

    for(int i=1;i<=n;i++) dis[i]=-1;dis[maxt]=0;

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]==-1)

            {

                dis[v]=dis[u]+e[i].x,q.push(v);fa[v]=u;w[v]=e[i].x;

                if(dis[v]>max1) max1=dis[v],maxt2=v;

            }

        }

    }

}

void bfs3()

{

    memset(dis,0,sizeof dis);

    for(int i=1;i<=n;i++)

      if(!b[i]) dis[i]=-1;

      else q.push(i);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]==-1)

            {

                dis[v]=dis[u]+e[i].x,q.push(v);fa[v]=u;w[v]=e[i].x;

                if(dis[v]>max1) max1=dis[v];

            }

        }

    }

}

bool check(int x)

{

    int ll=1,rr=tot;

    while(sum[ll]<=x&&ll<=tot) ll++;

    while(sum[tot]-sum[rr-1]<=x&&rr>=1) rr--;

    return sum[rr]-sum[ll-1]<=S;

}

void erfen()

{

    while(l<=r)

    {

        int mid=(l+r)>>1;

        if(check(mid)) ans=mid,r=mid-1;

        else l=mid+1;

    }

    return ;

}

void slove()

{

    int x=maxt2;r=dis[maxt2];

    while(x!=maxt)

    {

        s[++tot]=x;

        b[x]=true;

        sum[tot]=sum[tot-1]+w[x];

        x=fa[x];

    }

    b[maxt]=true;

    max1=0;bfs3();ans=l=max1;

    if(r>S) erfen();

}

int main()

{

    //freopen("mindist.in","r",stdin);

    //freopen("mindist.ans","w",stdout);

    int x,y,z;

    n=read(),S=read();

    for(int i=1;i<=n-1;i++)

    {

        x=read(),y=read(),z=read();

        add(x,y,z),add(y,x,z);

    }

    bfs1(),max1=0,bfs2(),slove();

    printf("%d",ans);

    return 0;

}

巴特西

Bzoj 2282: [Sdoi2011]消防(二分答案)

最新文章

热门文章