POJ P1741 Tree 解题报告

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

　　　　　　　　　　　　--by POJ

http://poj.org/problem?id=1741

点分治的相关题目；

有关点分治的内容；

题目大意为查询树上最短距离不大于k的点对个数；

我们应用点分治的思路，

统计在完全在某子树内经过其重心的路径；

然后再递归分治下去；

统计方式采取，dfs出子树中，点到重心的距离，查找合法（dis(i)+dis(j)≤k）的组合；

如何查找合法的组合？

 sort(dis+,dis+num+);

 r=num;

 for(l=;l<=num,l<r;l++){

     while(dis[l]+dis[r]>k&&l<r)

     　　r--;

     ans+=r-l;

 }

可以看出查找效率主要在排序上，反正很快；

但发现当两点在同一子树中且dis(i)+dis(j)≤k时，他们被计入答案，但他们的最短路径甚至不经过该重心；

于是把这些点用相似的方式查出再减去即可；

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

struct ss{

    int next,to,w;

};

ss e[];

int first[],num;

int n,k,ans,size[],max_size[],vis[],dis[];

inline void Init();

inline void build(int ,int ,int );

inline void part_dfs(int );

inline void dfs_size(int ,int );

inline int  dfs_root(int ,int ,int );

inline int  chan_ans(int ,int );

inline void dfs_len(int ,int ,int );

inline void in(int &ans)

{

    ans=;bool p=false;char ch=getchar();

    while((ch>'' || ch<'')&&ch!='-') ch=getchar();    if(ch=='-') p=true,ch=getchar();

    while(ch<=''&&ch>='') ans=ans*+ch-'',ch=getchar();    if(p) ans=-ans;

}

int main()

{

    int i,j,u,v,w;

    while(scanf("%d%d",&n,&k)==){

        if(n==)

            return ;

        Init();

        for(i=;i<=n-;i++){

            in(u),in(v),in(w);

            build(u,v,w);build(v,u,w);

        }

        part_dfs();

        printf("%d\n",ans);

    }

}

inline void Init(){

    memset(vis,,sizeof(vis));

    memset(first,,sizeof(first));

    ans=;num=;

}

inline void build(int f,int t,int wi){

    e[++num].next=first[f];first[f]=num;

    e[num].to=t;e[num].w=wi;

}

inline void part_dfs(int now){

    int root,i;

    dfs_size(now,);

    root=dfs_root(now,,now);

    ans+=chan_ans(root,);

    vis[root]=;

    for(i=first[root];i;i=e[i].next)

        if(!vis[e[i].to]){

            ans-=chan_ans(e[i].to,e[i].w);

            part_dfs(e[i].to);

        }

}

inline void dfs_size(int now,int fa){

    size[now]=;

    for(int i=first[now];i;i=e[i].next)

        if(!vis[e[i].to]&&e[i].to!=fa){

            dfs_size(e[i].to,now);

            size[now]+=size[e[i].to];

        }

}

inline int dfs_root(int now,int fa,int r){

    int i,root=-,wroot;

    max_size[now]=size[r]-size[now];

    for(i=first[now];i;i=e[i].next)

        if(!vis[e[i].to]&&e[i].to!=fa){

            if(size[e[i].to]>max_size[now])

                max_size[now]=size[e[i].to];

            wroot=dfs_root(e[i].to,now,r);

            if(max_size[wroot]<max_size[root]||root==-)

                root=wroot;

        }

    if(max_size[now]<max_size[root]||root==-)

        root=now;

    return root;

}

inline int chan_ans(int root,int dis1){

    int l,r,ans=;

    num=;

    dfs_len(root,dis1,);

    sort(dis+,dis+num+);

    r=num;

    for(l=;l<=num,l<r;l++){

        while(dis[l]+dis[r]>k&&l<r)r--;

        ans+=r-l;

    }

    return ans;

}

inline void dfs_len(int now,int d,int fa){

    dis[++num]=d;

    for(int i=first[now];i;i=e[i].next)

        if(!vis[e[i].to]&&e[i].to!=fa)

            dfs_len(e[i].to,d+e[i].w,now);

}

//点分治：

//dfs分治{

//对每个分支dfs（两遍）重心

//以重心为根dfs统计合法路径个数

//}分治重心的子树结构

//dis：一个不具有顺序的点到当前结构的重心的距离表

//vis[i]标记(染色)已到过的重心

//size[i]

//max_size[i]记录某点的最大子树大小；

//由于基于每个分支的dfs之间是跳着的（因为现在的重心未必是前重心的子节点），所以需要vis顺便截断某次dfs，防止跑出分支

祝AC

巴特西

POJ P1741 Tree 解题报告

最新文章

热门文章