[SDOI2011]消防

某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。

这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。

现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。

你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

Solution

这题非常神，神在它有一堆解法。

首先考虑无脑暴力，枚举一个起点，一个终点，O(n)算出最长距离，更新答案，复杂度O(n^3)。

然后根据贪心的想法，我们选择的链一定在树的直径上。

设直径端点为s和t

我们可以扫描直径上的每个点，对于每个点确定唯一的最远距离，在DFS一遍更新答案，复杂度O(n^2)。

然后发现答案具有单调性，可以二分一个答案，在直径两端贪心的找出能达到的不超过答案的最远点，DFS一遍检查合法性，复杂度O(nlogn)

继续观察我们可以发现，对于直径上的一个点i，我们要确定一个j使得max(dis(s,i),dis(j,t),sigma(d[k]))最小

d[k]表示从k点出发不经过直径上任何一个点能达到的最远距离,预处理可以得到。

于是O(n)的做法就出现了。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define N 300002

using namespace std;

queue<int>q;

bool vis[N];

int dis[N],tot,head[N],l1[N],nex[N],num,id,id2,s,n,ans,di,dis1[N],dis2[N],pre[N],l2[N];

struct zzh{

    int n,to,l;

}e[N<<];

inline void add(int u,int v,int l){

  e[++tot].n=head[u];

  e[tot].to=v;

  head[u]=tot;

  e[tot].l=l;

}

void dfs(int u,int fa){

    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa){

        int v=e[i].to;

        dfs(v,u);

        if(!vis[v])dis[u]=max(dis[u],dis[v]+e[i].l);

    }

}

int main(){

    scanf("%d%d",&n,&s);int u,v,w,an=;

    for(int i=;i<n;++i)scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);

    q.push();vis[]=;

    while(!q.empty()){

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

        for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){

            int v=e[i].to;

            dis[v]=dis[u]+e[i].l;

            vis[v]=;

            q.push(v);

            }

        }

    for(int i=;i<=n;++i)if(dis[i]>an){

       id=i;

       an=dis[i];

   }

   an=;memset(dis,,sizeof(dis));memset(vis,,sizeof(vis));

    q.push(id);vis[id]=;

    while(!q.empty()){

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

        for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){

            int v=e[i].to;

            dis[v]=dis[u]+e[i].l;

            pre[v]=u;

            l2[v]=e[i].l;

            vis[v]=;

            q.push(v);

            }

        }

    for(int i=;i<=n;++i)if(dis[i]>an){

        an=dis[i];

        id2=i;

    }

    memset(dis,,sizeof(dis));memset(vis,,sizeof(vis));

    ans=0x3f3f3f3f;

    for(int i=id2;i!=id;i=pre[i])l1[pre[i]]=l2[i],nex[pre[i]]=i;

    for(int i=id;i!=id2;i=nex[i])vis[i]=,dis1[i]=di,di+=l1[i];vis[id2]=;dis1[id2]=di;

    for(int i=id;i!=id2;i=nex[i])dis2[i]=di-dis1[i]; dis2[id2]=di-dis1[id2];

    dfs(id,);int diss=id;

    for(int i=id;i;i=nex[i]){

        while(dis1[diss]-dis1[i]+l1[diss]<=s&&diss!=id2)diss=nex[diss];

    //    cout<<i<<" qwq"<<diss<<" "<<dis1[i]<<" "<<dis2[diss]<<endl;

        ans=min(ans,max(dis1[i],dis2[diss]));

        if(diss==i)diss=nex[diss];

        if(i==id2)break;

    }

    for(int i=;i<=n;++i)if(vis[i])ans=max(ans,dis[i]);

    cout<<ans;

    return ;

}

巴特西

[SDOI2011]消防

最新文章

热门文章