[POJ1741]Tree(点分治)

发布于 2018-02-22  70 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[POJ1741]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.

Http

HDU

Tag

点分治

题目大意

给出一棵树,求其中路径长度不超过一个给定的数\(K\)的点对个数

解决思路

考虑点分治,每一层从当前根出发\(bfs\)求出深度,然后组合出所有不超过\(K\)的方案。但这样就会有不合法的情况,所以要减去不经过当前根的答案,再递归求解。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=10100;
const int maxM=maxN*2;
const int inf=2147483647;

int n,K,Ans;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM],W[maxM];
int root,Size[maxN],mxSon[maxN],nowsum;
bool vis[maxN];
int Depth[maxN],scnt,SortData[maxN];
int Queue[maxN],Fa[maxN];

void Add_Edge(int u,int v,int w);
void GetRoot(int u,int fa);
void Solve(int u);
int Calc(int u,int dep);

int main()
{
    ios::sync_with_stdio(false);
    while (cin>>n>>K)
    {
        if ((n==0)&&(K==0)) break;
        edgecnt=0;Ans=0;mem(Head,-1);mem(vis,0);
        for (int i=1;i<n;i++)
        {
            int u,v,w;cin>>u>>v>>w;
            Add_Edge(u,v,w);Add_Edge(v,u,w);
        }
        mxSon[0]=inf;
        root=0;nowsum=n;
        GetRoot(1,0);
        Solve(root);
        printf("%d\n",Ans);
    }
    return 0;
}

void Add_Edge(int u,int v,int w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
    return;
}

void GetRoot(int u,int fa)//求重心
{
    Size[u]=1;mxSon[u]=0;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((V[i]!=fa)&&(vis[V[i]]==0))
        {
            GetRoot(V[i],u);Size[u]+=Size[V[i]];
            mxSon[u]=max(mxSon[u],Size[V[i]]);
        }
    mxSon[u]=max(mxSon[u],nowsum-Size[u]);
    if (mxSon[u]<mxSon[root]) root=u;
    return;
}

void Solve(int u)//递归求解
{
    Ans+=Calc(u,0);
    vis[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            Ans-=Calc(V[i],W[i]);nowsum=Size[V[i]];
            root=0;GetRoot(V[i],0);
            Solve(root);
        }
    return;
}

int Calc(int u,int dep)//计算答案
{
    Depth[u]=dep;scnt=0;Fa[u]=0;
    int h=1,t=0;Queue[1]=u;
    do
    {
        int u=Queue[++t];
        SortData[++scnt]=Depth[u];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((vis[V[i]]==0)&&(V[i]!=Fa[u]))
            {
                Fa[V[i]]=u;Depth[V[i]]=Depth[u]+W[i];
                Queue[++h]=V[i];
            }
    }
    while (t!=h);
    sort(&SortData[1],&SortData[scnt+1]);
    int l=1,r=scnt,ret=0;
    while (l<r)
    {
        if (SortData[l]+SortData[r]<=K) ret=ret+r-l,l++;
        else r--;
    }
    return ret;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[POJ1741]Tree(点分治)


HNCJ OIer 一枚