程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj Tree（樹形dp）

poj Tree（樹形dp）

編輯：C++入門知識

poj Tree（樹形dp）

Tree Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 14706 Accepted: 4781

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.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

Source

LouTiancheng@POJ
題意：給定n個點的樹，求其中任意兩個點的距離<=k的對數。分析：分為兩種情況，一種是不同支的情況，這種好處理一些，直接往上找到公共父親權值相加就可以；另一種就是同支的情況，把重復的權值刪去就行了，只是實現起來麻煩些。另外推薦一篇博客詳解，我也是看的他的，很厲害。

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define ll long long
#define CL(a,b) memset(a,b,sizeof(a))
#define MAXN 20010

struct node
{
    int v,len;//v是鄰接點，len是權值
    int sum,bat;//sum是子節點個數，bat是拆當前點後子樹的最大結點數  
    node *next;
}tree[MAXN],*head[MAXN],dp[MAXN];
int n,k,ans,pre,root,tot;
int vis[MAXN],dist[MAXN];
int size[MAXN],sign[MAXN];//size表示最大分支的結點數,sign是一個hash數組  

void init()
{
    ans = pre = 0;
    for(int i=0; iv!=father&&vis[p->v]==0)
        {
            dfs(p->v, son);
            dp[son].sum += dp[p->v].sum;//累計子節點數
            dp[son].bat = max(dp[son].bat, dp[p->v].sum);//找最大分支
        }
        p = p->next;
    }
    dp[son].sum++;
    sign[tot] = son;//hash
    size[tot++] = dp[son].bat;//記錄每個最大分支的結點數  
}

int GetRoot(int son)
{
    tot = 0; dfs(son, 0);
    int maxx=INF, maxi, cnt=dp[son].sum;
    for(int i=0; iv!=father&&vis[p->v]==0&&dis+p->len<=k)
            GetDist(p->v, son, dis+p->len);
        p = p->next;
    }
}

void count1(int son)//不同支
{
    sort(dist, dist+tot);
    int left=0, right=tot-1;
    while(left < right)
    {
        if(dist[left]+dist[right] <= k)
            ans += (right - left), left++;
        else right--;
    }
}

void count2(int son)//同支
{
    vis[son] = 1;
    node *p = head[son];
    while(p != NULL)
    {
        if(vis[p->v] == 0)
        {
            tot = 0; GetDist(p->v, son, p->len);
            sort(dist, dist+tot);
            int left=0, right=tot-1;
            while(left < right)
            {
                if(dist[left]+dist[right] <= k)
                    ans -= (right - left), left++;
                else right--;
            }
        }
        p = p->next;
    }
}

int solve(int son, int father)
{
    root = GetRoot(son);
    tot=0;
    GetDist(root, 0, 0);
    count1(root);
    count2(root);
    node *p = head[root];
    while(p != NULL)
    {
        if(p->v!=father&&vis[p->v]==0)
            solve(p->v, root);
        p = p->next;
    }
}

int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&k),n+k)
    {
        init();
        for(int i=1; i