[SDOI2011]消防-白红宇

[SDOI2011]消防

阅读量：5139 次

发布时间：2019-06-13

本文共 2478 字，大约阅读时间需要 8 分钟。

毒瘤的树上问题

这道题是树网的核的加强版：观察题目，我们会发现，那条修建的路径一定在树的直径上：那么我们首先通过两边bfs求出树上直径，再通过dfs求出直径的点和直径上的前缀和。然后我们二分答案，二分一个最远距离，如何check呢？我们要用一点逆向思维：考虑通过头，尾指针的移动：头指针初始在一个端点，尾指针在另一个端点。每次都尽量向中间靠拢，直到最大距离超过mid为止，然后检查一下路径的长度是否超过限制就好了。

// luogu-judger-enable-o2#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
            #include
           
            using namespace std;const int maxn=1000006;const int INF=1e9+7;int head[maxn],cur;struct hzw{ int to,next,v;}e[maxn];typedef pair
            
             p;inline void add(int a,int b,int c){ e[cur].to=b; e[cur].next=head[a]; e[cur].v=c; head[a]=cur++;}int fina,mx,col[maxn],s,n;bool vis[maxn];inline void bfs(int now){ queue
             q; memset(vis,0,sizeof(vis)); fina=0; mx=-23333; q.push(p(now,0)); while (!q.empty()) { p all=q.front(); q.pop(); int s=all.first,cost=all.second; vis[s]=1; if (cost>mx) { mx=cost; fina=s; } for (int i=head[s];i!=-1;i=e[i].next) { int vv=e[i].to; if (vis[e[i].to]) continue; q.push(p(e[i].to,cost+1)); } }}int sum[maxn],rod[maxn],rcnt,dis[maxn];inline bool dfs(int s,int fa){ if (s==fina) { rod[++rcnt]=s; sum[rcnt]=0; return 1; } for (int i=head[s];i!=-1;i=e[i].next) { if (e[i].to==fa) continue; if (dfs(e[i].to,s)) { rod[++rcnt]=s; sum[rcnt]=sum[rcnt-1]+e[i].v; return 1; } } return 0;}inline void dfs2(int s,int fa){ dis[s]=0; vis[s]=1; for (int i=head[s];i!=-1;i=e[i].next) { if (e[i].to==fa||vis[e[i].to]) continue; dfs2(e[i].to,s); dis[s]=max(dis[s],dis[e[i].to]+e[i].v); }}int now[maxn];inline bool check(int k){ sum[rcnt+1]=sum[rcnt]; for (int i=1;i<=rcnt;++i) { if (dis[rod[i]]) now[i]=k-dis[i]; } int firs=1,las=rcnt,mx=INF; int lmx=0,rmx=0; while (1) { lmx=sum[firs]; if (lmx>k) { firs--; break; } mx-=sum[firs]-sum[firs-1]; if (mx<0) { firs--; break; } if (dis[rod[firs]]&&now[firs]
              
               k) { las++; break; } if (mx<0) { las++; break; } if (dis[rod[las]]&&now[las]
               
                s) return 0; return 1;}inline int solve(){ int l=0,r=sum[rcnt],ans=r; for (int i=1;i<=rcnt;++i) { l=max(l,dis[rod[i]]); } while (l<=r) { int mid=(l+r)>>1; if (check(mid)) { ans=min(ans,mid); r=mid-1; } else l=mid+1; } return ans;}int main(){ memset(head,-1,sizeof(head)); cin>>n>>s; for (int i=1,a,b,c;i<=n-1;++i) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } bfs(1); int tmp1=fina; bfs(tmp1); dfs(tmp1,tmp1); memset(vis,0,sizeof(vis)); for (int i=1;i<=rcnt;++i) vis[rod[i]]=1; for (int i=1;i<=rcnt;++i) { dfs2(rod[i],rod[i]); } cout<

转载于:https://www.cnblogs.com/bullshit/p/9801769.html

你可能感兴趣的文章