ZOJ 3684 Destroy 树的直径+二分 - c++编程基础

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do problemCode=3684

题意：题中给出一个树，结点是城市，路径有长度和炸毁需要的武器单位数，，X单位的武器能同时炸毁所有X单位以下的路径。问需要多少单位的武器能使所有边疆城市和中心城市不联通。

思路：中心城市就是整棵树的根（到所有城市中的最长距离最短的城市），树的根一定在树的直径上。两次DFS找到树的直径，枚举找到根（姿势不够优美，更好的方式是树形DP）。然后进行二分枚举炸弹单位数判断联通性即可。

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #define PI acos(-1.0) #define maxn 10005 #define INF 1<<25 #define MAX 0x7fffffff typedef long long ll; using namespace std; struct Edge { int v; long long w,a; int next; } edge[maxn*2]; int head[maxn],vis[maxn],leaf[maxn]; long long dist[maxn],way[maxn],rc[maxn]; int now=0,A=0,s=0,top=0; long long ttt=0; int add_edge(int u,int v,int w,int a) { edge[top].v=v; edge[top].w=w; edge[top].a=a; edge[top].next=head[u]; head[u]=top++; edge[top].v=u; edge[top].w=w; edge[top].a=a; edge[top].next=head[v]; head[v]=top++; return 0; } int ans=0; int dfs(int x) { if(ans>s) s=ans; vis[x]=1; for(int i=head[x]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(!vis[v]) { ans+=edge[i].w; dist[v]=ans; dfs(v); ans-=edge[i].w; } } return 0; } int dfs3(int x,int root) { vis[x]=1; rc[now++]=x; if(ans>ttt) { ttt=ans; A=now; for(int i=0; i
             
              bomb) { dfs2(v,bomb); } } return 0; } int main() { int t; while(scanf("%d",&t)!=EOF) { top=0,ttt=0,now=0,A=0,ans=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); for(int i=1; i
              
               d) { L=i; d=dist[i]; } memset(vis,0,sizeof(vis)); ans=0; dfs3(L,L); int R=-1; long long ss=-1; for(int i=0; i
               
                l) { memset(vis,0,sizeof(vis)); mid=(r+l)/2; dfs2(R,mid); int flag=0; for(int i=0; i