首页 > 搜索 > DFS搜索 > HDU 3290-The magic apple tree-DFS-[解题报告]HOJ
2014
03-13

HDU 3290-The magic apple tree-DFS-[解题报告]HOJ

The magic apple tree

问题描述 :

Sailormoon girls all like eating many kinds of fruit, such as banana, grape, apple and so on.
One day, when they was walking on a orchard, they found a magic apple tree.The magic apple tree have many nodes,but there is only one root. Each notes has its label. It is labeled from 1.On the first day,only each leaf nodes(has no children nodes) have apples. Any other nodes have no apples. The number of apples that each leaf nodes have is just the label of this node.When all the immediate children of a node each has apples,this node will grow some apple on the next day. If a node has K immediate children node,the number of apple that this node grow on next day is just the number of apples that the (K + 1) / 2th smaller node has.The Xth smaller node means there are X � 1 nodes’ number of apples is less than this node’s number of apple.
Now you task is to calculate the number of apples that the root has at last.

输入:

There are multiple test cases.
Each case contains a positive integer N, it means this tree has N nodes, labeled 1, 2, … N(0 < N <= 20000).
The following N lines describe the children of all nodes in order of their labels. The (X + 1)th line in each test case starts with a number p (0 <= p <N), it means the Xth node has p immediate children nodes.then followed by p positive integer, means the label of immediate child node

输出:

There are multiple test cases.
Each case contains a positive integer N, it means this tree has N nodes, labeled 1, 2, … N(0 < N <= 20000).
The following N lines describe the children of all nodes in order of their labels. The (X + 1)th line in each test case starts with a number p (0 <= p <N), it means the Xth node has p immediate children nodes.then followed by p positive integer, means the label of immediate child node

样例输入:

7
2 2 3
2 5 4
2 6 7
0
0
0
0

12
3 2 3 4
0
2 5 6
3 7 8 9
3 10 11 12
0
0
0
0
0
0
0

样例输出:

4
6

也算树形dp?~~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=30000;
const int MAXM=50000;
struct node
{
    int u,v;
};
node edge[MAXM];
int first[MAXN],next[MAXM];
int cc;
int num[MAXN];
int child_num[MAXN];
int in[MAXN];
inline void add_edge(int u,int v)
{
    edge[cc].u=u;
    edge[cc].v=v;
    next[cc]=first[u];
    first[u]=cc;
    cc++;
}
void dfs(int u)
{
    if(num[u]!=-1)
        return ;
    int i;
    int k=0;
    int *temp=new int[MAXN];
    for(i=first[u];i!=-1;i=next[i])
    {
        int v=edge[i].v;
        dfs(v);
        temp[k++]=num[v];
    }
    sort(temp,temp+k);
    num[u]=temp[(child_num[u]+1)/2-1];
    delete temp;
    return ;
}
void Scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        memset(first,-1,sizeof(first));
        memset(next,-1,sizeof(next));
        cc=0;
        memset(num,-1,sizeof(num));
        memset(in,0,sizeof(in));
        memset(child_num,0,sizeof(child_num));
        for(i=1;i<=n;i++)
        {
            int p;
            Scan(p);
            child_num[i]=p;
            if(p==0)
                num[i]=i;
            int j;
            for(j=0;j<p;j++)
            {
                int x;
                Scan(x);
                in[x]++;
                add_edge(i,x);
            }
        }
        for(i=1;i<=n;i++)
            if(in[i]==0)
            {
                dfs(i);
                break;
            }
        printf("%d\n",num[i]);
    }
    return 0;
}

参考:http://blog.csdn.net/juststeps/article/details/9397717


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。