算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    给你一个N(N<10000)个点的有权树,请问距离不超过K(K<1,000,000,000)的点对有多少个?

吐槽:

    1. 大家想不想看男人八题的总结? 有需求的话我就一天写一篇~~~~ (之前切了3道...不过写的很挫)
    2. 代码写的很挫,加上各种注释/调试语句干了2.5k...
    3. 说好的今天学块链呢...


算法分析:

    又是一道计数问题,总的想法是分治然后容斥...
    对于一个有根树,计算路径经过root的点对的个数。如果被计算出来了,再去计算它的子树。
    问题是如何保证它的子树分布的比较“均匀”呢?  有个定理:
        存在一个点使得分出的子树的结点个数均不大于 N / 2 (证明略)
    我们的目的就是找到一个这样的点,即树的重心(可能有多个)。
    做法就是从任意一点开始做树形DP,对于某个点u判断每个子树的sum值和SUM-sum[u]的值是否全部不大于n/2...
    
    分(divide)的问题解决了,那么如果治(conquer)呢?
    我们要求经过root且长度不超过K的所有路径,也就是求所有(deep[u]+deep[v]<=K ----- 1) (u,v不在同一个root的儿子下面)的点对(deep[u]是值u到root的距离)
    直接求“u,v不属于同一个root的儿子”的点对总数比较困难,我们可以容斥着做:
    ans = (所有满足1式的点对) - (root的儿子 a(1...m)下面所有满足1式的点对) (计算m次)
    计算一次所有满足1式的点对的方法是
        1. 根据deep值从小到大排序
        2. 扫一遍,维护一个值left,使left是val[left] + val[i] <=K的最大值
    这样分治的每一层时间复杂度是O(NlogN)
    一共分治logN层 总复杂度(N*(logN)^2)
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cassert>
  4 #include<algorithm>
  5 using namespace std;
  6 #define re(i,n) for(int i=0;i<n;i++)
  7 #define re3(i,n) for(int i=1;i<n;i++)
  8 int n,e,size,g,len,k,__ANS;
  9 const int V = 10005;
 10 const int E = V*2;
 11 int head[V] , nxt[E] , pnt[E], hash[E], cost[E], sum[V], tmp[V], dep[V];
 12 template <typename T> inline void chkmax(T &a, const T b) {if(a < b) a = b;}
 13 void dfs(int u,int f){
 14     sum[u] = 1;
 15     bool flag = 0;
 16     for(int i = head[u]; i != -1; i = nxt[i]){
 17         if(hash[i]) continue;
 18         int v = pnt[i];
 19         if(v == f) continue;
 20         dfs(v,u);
 21         if(sum[v] > size /2) flag = 1;
 22         sum[u] += sum[v];
 23 //        cout<<"u: "<<u<<" v: "<<v<<" "<<sum[v]<<endl;
 24     }
 25     if(!flag && sum[u] > size/2) g = u;
 26 //    cout<<"u: "<<u<<" "<<sum[u]<<endl;
 27 }
 28 void dfs1(int u,int f,int d){
 29     dep[u] = d;
 30     tmp[len++] = d;
 31     for(int i = head[u]; i!= -1;i=nxt[i]){
 32         if(hash[i]) continue;
 33         int v = pnt[i];
 34         if(v == f) continue;
 35         dfs1(v,u,d+ cost[i]);
 36     }
 37 }
 38 void dfs2(int u,int f){
 39     tmp[len++] = dep[u];
 40     for(int i = head[u]; i!=-1; i=nxt[i]){
 41         if(hash[i]) continue;
 42         int v = pnt[i];
 43         if(v!=f) dfs2(v,u);
 44     }
 45 }
 46 int cal_SUM(){
 47     int SUM = 0,l=0;
 48     sort(tmp,tmp+len);
 49 //    re(i,len) cout<<tmp[i]<<" "; cout<<endl;
 50     re3(i,len){
 51         while(tmp[l]+tmp[i]>k) l --;
 52         l ++;
 53         SUM += l;
 54     }
 55 //    cout<<"SUM: "<<SUM<<endl;
 56     return SUM;
 57 }
 58 int dfs3(int u,int f){
 59     sum[u] = 1;
 60     for(int i= head[u];i!=-1;i=nxt[i]){
 61         if(hash[i] || pnt[i]==f) continue;
 62         else sum[u] += dfs3(pnt[i],u);
 63     }
 64     return sum[u];
 65 }
 66 void cal(int x,int s){
 67     g = -1, size = s;
 68 //    cout<<x<<" "<<s<<endl;
 69     dfs(x,x);
 70     assert(g>=0);
 71 //    cout<<g<<endl;
 72     //// find zhongxin
 73     len = 0;
 74     dfs1(g,g,0);
 75     assert(len == size);
 76     int SUM = cal_SUM();
 77     for(int i = head[g]; i!=-1; i=nxt[i]){
 78         if(hash[i]) continue;
 79         int v= pnt[i];
 80         hash[i] = hash[i^1] = 1;
 81         len = 0;
 82         dfs2(v,v); SUM -= cal_SUM();
 83         hash[i] = hash[i^1] = 0;
 84     }
 85     __ANS += SUM;
 86 //    cout<<SUM<<endl;
 87     dfs3(g,g);
 88     ///// CAL SUM
 89     for(int i = head[g]; i!=-1;i=nxt[i]){
 90         if(hash[i]) continue;
 91         int v = pnt[i];
 92         hash[i] = hash[i^1] = 1;
 93         cal(v, sum[v]);
 94         hash[i] = hash[i^1] = 0;
 95     }
 96     // DIVIDE AND CONQURE
 97 }
 98 void add_edge(int u,int v,int c){
 99     nxt[e] = head[u];
100     head[u] = e;
101     pnt[e] = v;
102     cost[e++] = c;
103 }
104 int main(){
105     while(~scanf("%d%d",&n,&k) && !(!n&&!k)){
106         re(i,n) head[i] = -1;
107         int u,v,c;
108         e = 0;
109         re(i,n-1) {
110             scanf("%d%d%d",&u,&v,&c);
111             add_edge(u-1,v-1,c); add_edge(v-1,u-1,c);
112         }
113         __ANS = 0;
114         cal(0,n);
115         printf("%d\n",__ANS);
116     }
117     return 0;
118 }
119 
posted on 2012-05-02 16:58 西月弦 阅读(455) 评论(0)  编辑 收藏 引用 所属分类: 解题报告经典题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理