HrbustOJ 1774 succession 递归 NCPC 2010

z4zr 2013-06-03 PM 2308℃ 0条

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1774

题目大意

国王快死掉了,然后 他要找个继承人,所以要在候选人中找一个血缘关系最大的人。。。
国王口味很重,所以关系很乱 但是 自己不能生出自己 放心吧

输入

N M      N个生育关系(孩子 父母1 父母2)M个候选人
国王的名字
N行 生育关系
M行 候选人

输出

继承人

Sample Input

4 5
andrew
betsy andrew flora
carol andrew betsy
dora andrew carol
elena andrew dora
carol
dora
elena
flora
gloria

Sample Output

elena

训练的时候 听了唯斌的想法 然后就啪啪啪啪啪。。。

然后莫名其妙的WA WA WA

跟五姑娘打赌找到数据X掉我 保养一周 无果。。。。。

加题后果断回忆。。。

问题出在 if( buffer > maxn)
原先是 if(buffer - maxn > eqs)
由于初始化的时候 node[i].n都是负数
在查询的时候可能会导致 出现正数+负数的溢出
(感谢群里面活泼的大家 撒)
以后如果不注重精度就尽量不使用第二个方法判断了。。。

#include<cstdio>
#include<cstring>
#define eqs 1e-8

struct Node
{
    char name[12];
    char p1[12],p2[12];
    double n;
} node[55];

int N,M;
char king[12],isking[12];
char buf[12];
double maxn,buffer;

double DFS(char *str)
{
    int pp;
    if(strcmp(str,king)==0)return 10000.0;
    else
    {
        pp=0;
        for(int i=1; i<=N; i++)
        {
            if(strcmp(str,node[i].name)==0)
            {
                pp=i;
                break;
            }
        }
        if(pp==0)return 0.0;
        if(node[pp].n>eqs)return node[pp].n;
        node[pp].n=(DFS(node[pp].p1)+DFS(node[pp].p2))/2.0;
        return node[pp].n;
    }
}

int main()
{
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        scanf("%s",king);
        for(int i=1; i<=N; i++)
        {
            scanf("%s %s %s",node[i].name,node[i].p1,node[i].p2);
            node[i].n=0;
        }
        maxn=-1000.0;
        for(int i=0; i<M; i++)
        {
            scanf("%s",buf);
            buffer = DFS(buf);
            if( buffer > maxn)
            {
                maxn = buffer;
                strcpy(isking,buf);
            }
        }
        puts(isking);
    }
    return 0;
}
标签: dfs, hrbust, 记忆化, 递归, acm

非特殊说明,本博所有文章均为博主原创。

评论啦~