ACM模版

描述

题解

很简单的一道题，不过出题有些坑了，一看题就知道，这是一个搜索问题，dfs、bfs 都可以用，存储树时我选择的是邻接表，但是却一直24分，拿不到25分。纠结死我了。后来了解到，问题出在 N 为 1 的时候，也就是说只有一个人，既是太师傅，又是得道者（这也太没溜了，一个徒弟也收不了还叫得道者），其实这个我早就想到了，只是有一点我感觉是这个题出的问题，因为题目中说了 Z 是太师傅的功力值，理论上讲，如果是这样的话，就算他是得到者也不能再翻倍了，因为他没有师傅，直接给定了他的功力，再翻倍怎么说得过去呢？我就是因为这个思维，无限24……后来一个朋友说，他也许是孙悟空一样的男人，一言不合就超赛，仔细一想，大概其他是弗利沙一样的男人吧！！！

代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 10;

vector<int> v[MAXN];

int N;
double Z, r;
double p[MAXN];
double sum = 0;

void dfs(int root)
{
    for (int i = 0; i < v[root].size(); i++)
    {
        if (p[v[root][i]] != 1)
        {
            p[v[root][i]] = p[root] * r * p[v[root][i]];
            sum += p[v[root][i]];
        }
        else
        {
            p[v[root][i]] = p[root] * r;
            dfs(v[root][i]);
        }
    }
}

int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    cin >> N >> Z >> r;
    r = (100 - r) / 100;

    for (int i = 0; i < N; i++)
    {
        p[i] = 1;
    }
    p[0] = Z;

    int K, nt;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &K);
        if (K == 0)
        {
            scanf("%lf", p + i);
            continue;
        }
        for (int j = 0; j < K; j++)
        {
            scanf("%d", &nt);
            v[i].push_back(nt);
        }
    }

    if (N == 1)
    {
        printf("%d\n", (int)(p[0] * Z));
        return 0;
    }

    dfs(0);

    printf("%d\n", (int)sum);

    return 0;
}