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

Poj 1655 Balancing Act (DP_樹形DP)

編輯:關於C

題目大意:給定一棵n棵節點的樹,刪去某個節點後剩下來的分支中肯定會有最大節點數,求所有節點的最大分支節點數的最小值。

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

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

代碼:
[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],ansval,ansi,cnt; 
 
 
void Initial() { 
 
    cnt = ptr = 0; 
    ansval = ansi = 2147483647; 
    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; 
    } 
}   www.2cto.com
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 (tot < n - dp[son]) 
        tot = n - dp[son]; 
    if (tot < ansval) 
        ansval = tot,ansi = son; 

 
 
int main() 

    int i,j,k,a,b,t; 
 
 
    scanf("%d",&t); 
    while (t--) { 
     
        scanf("%d",&n); 
        Initial(); 
        for (i = 1; i < n; ++i) { 
 
            scanf("%d%d",&a,&b); 
            AddEdge(a,b); 
        } 
 
 
        Dfs_Ini(1,0);           //第一次深搜,記錄當前節點的子孫總數 
        Dfs_Solve(1,0);         //更新答案 
        printf("%d %d\n",ansi,ansval); 
    } 

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