POJ 1741 Tree 树形DP（分治） - c++编程基础

TOP

POJ 1741 Tree 树形DP（分治）

2015-07-20 17:46:40 来源: 作者: 【大中小】浏览:2次

题意：给出一棵树，节点数为N（N<=10000），给出N-1条边的两点和权值，给出数值k，问树上两点最短距离小于k的点对有多少个。

思路：拿到题的第一反应是LCA问题，不过细一想询问次数极限情况可以达到10000*5000次，即使用Tarjan也是超时没商量的。

2009年国家队论文提供了树的分治思想，对于本题就是树的分治的点分治的应用。每次找到能使含节点最多的子树的节点最少的根分而治之，同样方式分别处理它的所有子树，知道处理到单独的节点。这样可以使复杂度最低化。（具体找根的方式和上一题思想类似，传送门：http://blog.csdn.net/ooooooooe/article/details/38981129 ）

对于每个根，记录其他点到根的距离，我要找出它的两个子节点分别处于它的不同子树并且距离小于k的情况数，不记录在同一子树的情况是因为对于同一子树的两个节点，它们的最短距离并不是它们到根的距离之和，而且如果对于每个根都记录处于相同子树的节点，那么会记重复情况。具体处理的方式是先记录到根距离之和小于等于k的点对的数量，然后对于每个子树分别除去在子树中到根距离之和小于等于k的点对的数量。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define eps 1e-8 #define INF 1000000000 #define maxn 10005 #define PI acos(-1.0) #define seed 31//131,1313 typedef long long LL; typedef unsigned long long ULL; using namespace std; int dp[maxn][2],from[maxn],head[maxn],all[maxn],top,tot,ans=0; int T,k,x,y,z; bool vis[maxn]; void init() { memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); ans=0; top=0; } struct Edge { int v,w; int next; } edge[maxn*2]; void add_edge(int u,int v,int w) { edge[top].v=v; edge[top].w=w; edge[top].next=head[u]; head[u]=top++; } void dfs_first(int u,int f) { from[u]=u; dp[u][0]=dp[u][1]=0; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v,w=edge[i].w; if(v==f||vis[v]) continue; dfs_first(v,u); if(dp[v][0]+w>dp[u][0]) { from[u]=v; dp[u][1]=dp[u][0]; dp[u][0]=dp[v][0]+w; } else if(dp[v][0]+w>dp[u][1]) dp[u][1]=dp[v][0]+w; } } void dfs_second(int u,int f,int k,int &root,int &deep) { if(u!=f) if(from[f]!=u) { if(dp[f][0]+k>dp[u][0]) { from[u]=f; dp[u][1]=dp[u][0]; dp[u][0]=dp[f][0]+k; } else if(dp[f][0]+k>dp[u][1]) dp[u][1]=dp[f][0]+k; } else { if(dp[f][1]+k>dp[u][0]) { from[u]=f; dp[u][1]=dp[u][0]; dp[u][0]=dp[f][1]+k; } else if(dp[f][1]+k>dp[u][1]) dp[u][1]=dp[f][1]+k; } if(dp[u][0]
                
                 k&&b>a) b--; ans+=b-a; a++; } vis[root]=1; for(int i=head[root]; i!=-1; i=edge[i].next) { tot=0; int v=edge[i].v,w=edge[i].w; if(!vis[v]) { dfs_third(v,0,w); sort(all,all+tot); a=0,b=tot-1; while(a
                 
                  k&&b>a) b--; ans-=b-a; a++; } dfs(v); } } } int main() { while(scanf(%d%d,&T,&k)) { if(!T&&!k) break; init(); for(int i=0; i
                  
                   ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Responsive design for tables	下一篇：Codeforces 107B Basketball Team..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: