hdu5044(二分)-白红宇

hdu5044(二分)

阅读量：4328 次

发布时间：2019-06-06

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

题意：一个树上建两个加油站。使得全部点到达其近期加油站的最大距离最小。

解法：二分答案。关键时二分时候，要最合理话布局两个点的位置，做法是处理出来树的直径，然后在直径两端分别向中间移动二分的x步的两个点布下加油站。

贪心能够证明正确性；

代码：

/******************************************************* @author:xiefubao*******************************************************/#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 //freopen ("in.txt" , "r" , stdin);using namespace std;#define eps 1e-8#define zero(_) (_<=eps)const double pi=acos(-1.0);typedef long long LL;const int Max=200010;const LL INF=0x3FFFFFFF;vector
                 
                   vec[Max];int n;vector
                  
                    diameter;int rem[Max];int rem1[Max];int rem2[Max];int dis[Max];int st,en;int dui[Max*2];int now=0;int count1=10;void dfs(int u){ memset(rem,0,sizeof rem); rem[u]=-1; int left=0; int right=1; dui[0]=u; dis[u]=0; while(left
                   
                    >t; while(t--) { for(int i=1;i
                    
                     d) { d=dis[i]; st=i; } } dfs(st); d=0; for(int i=1; i<=n; i++) { if(dis[i]>d) { d=dis[i]; en=i; } } while(en!=-1) { diameter.push_back(en); en=rem[en]; } int left=0,right=diameter.size(); while(left<=right) { int middle=(left+right)/2; if(!OK(middle)) { left=middle+1; } else { right=middle-1; } } int a=diameter[left]; int b=diameter[diameter.size()-1-left]; if(a==b) { a=b==n?n-1:b+1; } //cout<
                     
                      <<" "<
                      
                       <
                       
                        <