[UVA][樹形DP] 10459 - The Tree Root＠Morris' Blog

2012-07-09 14:28:56| 人氣1,880| 回應0 | 上一篇 | 下一篇

[UVA][樹形DP] 10459 - The Tree Root

推薦 0 收藏 0 轉貼0 訂閱站台

Problem G
The Tree Root
Input: standard input
Output: standard output
Time Limit: 4 seconds
 
 Tree is an important data structure. Searching is a basic operation in any
data structure. In a tree searching mainly depends on its height. Consider the following three trees.




If you observe carefully, you will see that all trees are same except 
different nodes are used as roots. Here
the height of the tree varies with the selection of the root. In the 1st
 tree root is '2' and height is 3. In 2nd one root is '1' and height is 
2. And in last one root is '4'
and height is 4. We will call '1' best root as it keeps the tree with 
the least possible height and '4' worst root for the
opposite reason.

In this problem, you have to find out all best roots and worst roots for a given tree.
 
Input
 Each dataset starts with a positive integer  N(3<=N<=5000),
which is the number of nodes in the tree. Each node in the tree has a unique id from 1 to N.
Then successively for each i'th node there will be a positive integer  K[i]  following id of K[i] nodes which are adjacent 
to i. Input is terminated by EOF.

Output
 For each dataset print two lines. In the 1st line show all the best roots
in ascending order and in next line show all worst roots in ascending order. See sample output for exact format.


 
Sample Input


7

2 2 3

3 1 6 7

3 1 4 5

1 3

1 3

1 2

1 2

Sample Output


Best Roots  : 1

Worst Roots : 4 5 6 7

做法 : 兩次 dfs,
1st dfs :
得到由下而上的最大高度 (要記錄第一高第二高),
意即得到每個節點的 subtree 的高度
2nd dfs :
將父節點高度轉過來, 這時要注意, 如果第一高是從這個節點接上去的, 那麼就抓第二高+1,

#include <stdio.h>
#include <algorithm>
#include <vector>
#define oo 0xfffffff
using namespace std;
vector<int> edge[5001];
int dp_down[5001][2], dp_up[5001];
int used[5001];
void dfs(int nd) {
    for(vector<int>::iterator i = edge[nd].begin(); i != edge[nd].end(); i++) {
        if(used[*i] == 0) {
            used[*i] = 1;
            dfs(*i);
            if(dp_down[*i][0]+1 > dp_down[nd][1])
                dp_down[nd][1] = dp_down[*i][0]+1;
            if(dp_down[nd][1] > dp_down[nd][0])
                swap(dp_down[nd][0], dp_down[nd][1]);
        }
    }
}
void dfs2(int nd, int v) {
    dp_up[nd] = v;
    for(vector<int>::iterator i = edge[nd].begin(); i != edge[nd].end(); i++) {
        if(used[*i] == 0) {
            used[*i] = 1;
            int hv;
            if(dp_down[*i][0]+1 != dp_down[nd][0])
                hv = dp_down[nd][0];
            else
                hv = dp_down[nd][1];
            hv = max(hv, dp_up[nd]);
            dfs2(*i, hv+1);
        }
    }
}
int main() {
    int n, m, i, y;
    while(scanf("%d", &n) == 1) {
        for(i = 1; i <= n; i++) {
            edge[i].clear();
            scanf("%d", &m);
            while(m--) {
                scanf("%d", &y);
                edge[i].push_back(y);
            }
            dp_down[i][0] = 0;
            dp_down[i][1] = 0;
            dp_up[i] = 0;
            used[i] = 0;
        }
        used[1] = 1;
        dfs(1);
        for(i = 1; i <= n; i++) used[i] = 0;
        used[1] = 1;
        dfs2(1, 0);
        int root[5001], best = oo, worst = 0;
        for(i = 1; i <= n; i++) {
            root[i] = max(max(dp_down[i][0], dp_down[i][1]), dp_up[i]);
            best = min(root[i], best);
            worst = max(root[i], worst);
        }
        printf("Best Roots :");
        for(i = 1; i <= n; i++)
            if(root[i] == best)
                printf(" %d", i);
        printf("\nWorst Roots :");
        for(i = 1; i <= n; i++)
            if(root[i] == worst)
                printf(" %d", i);
        puts("");
    }
    return 0;
}

我要檢舉

#10459#The Tree Root

台長： Morris

您可能對以下文章有興趣

[UVA] 886 - Named Extension Dialing

[UVA][IDA*] 11163 - Jaguar King

[UVA] 227 - Puzzle

[UVA][TSP] 11405 - Can U Win?

人氣(1,880) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 1226 - Numerical surprises
此分類上一篇:[UVA][JAVA] 485 - Pascal's Triangle of Death

回應(0)