程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> Poj 2378 Tree Cutting (DP_樹形DP)

Poj 2378 Tree Cutting (DP_樹形DP)

編輯:關於C語言

題目大意:給定一棵n棵節點的樹,如果刪去某個節點使得剩下來的最大分支節點數小等於節點總數的一半則這個刪除就是叼爆的,問叼爆的刪法總數。

解題思路:樹形DP.深搜兩次,第一次深搜記錄從當前節點的子孫節點總數(包括自己),第一次算預處理,復雜度為O(N),第二次利用第一次的結果找各分支的最大節點數,分支有兩種情況,一種是孩子的分支,一種當前節點到父親節點的那條分支(總數為N-dp[cur]),這樣再算N次即可得解。

測試數據:
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

代碼:
[html] 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
#define MAX 110000 
#define max(a,b) (a)>(b)?(a):(b) 
 
 
struct node { 
 
    int v; 
    node *next; 
}*head[MAX],tree[MAX]; 
int n,m,ptr,dp[MAX],ans[MAX],cnt; 
 
 
void Initial() { 
 
    cnt = ptr = 0; 
    memset(dp,0,sizeof(dp)); 
    memset(head,NULL,sizeof(head)); 

void AddEdge(int x,int y) { 
 
    tree[ptr].v = y; 
    tree[ptr].next = head[x],head[x] = &tree[ptr++]; 
    tree[ptr].v = x; 
    tree[ptr].next = head[y],head[y] = &tree[ptr++]; 

void Dfs_Ini(int s,int pa) { 
 
    dp[s] = 1; 
    node *p = head[s]; 
    while (p != NULL) { 
 
        if (p->v != pa) { 
 
            Dfs_Ini(p->v,s); 
            dp[s] += dp[p->v]; 
        } 
        p = p->next; 
    } 

void Dfs_Solve(int son,int pa) { 
 
    int i,j,tp,tot = 0; 
    node *p = head[son]; 
     
 
    while (p != NULL) { 
 
        if (p->v != pa) { 
 
            Dfs_Solve(p->v,son); 
            tp = dp[p->v]; 
            tot = max(tot,tp); 
        } 
        p = p->next; 
    } 
    if (n - dp[son] <= n / 2 && tot <= n / 2)  
        cnt++,ans[cnt] = son; 

 
 
int main() 

    int i,j,k,a,b; 
 
 
    while (scanf("%d",&n) != EOF) { 
 
        Initial(); 
        for (i = 1; i < n; ++i) { 
 
            scanf("%d%d",&a,&b); 
            AddEdge(a,b); 
        } 
 
 
        Dfs_Ini(1,0);           //第一次深搜,記錄當前節點的子孫總數 
        Dfs_Solve(1,0);         //更新答案 
        sort(ans+1,ans+1+cnt);  //按字典序輸出 
        for (i = 1; i <= cnt; ++i) 
            printf("%d\n",ans[i]); 
        if (cnt == 0) printf("NONE\n"); 
    } 


作者:woshi250hua

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved