CCCC L2-020. 功夫传人 搜索 bfs && 精度+ 特判

时间：2023-12-28 19:30:14

https://www.patest.cn/contests/gplt/L2-020

题解：给你一颗树，让你遍历一遍，顺便更新一下数据，每次到根节点时将其对应的数据加到ans上面。这里用的bfs。

坑：1.卡精度：float会wa ，要用double

　　2.卡特殊情况：只有根节点

　　3.//类型转换表达式要加两个括号

　　//4.题意不明啊，什么叫  减弱r，除非得道。？



技巧：卡样例：写一句if（n==1) return 1 ;如果某个样例显示    返回非零   就说明。。。你懂的。ps：某个样例只有一份一般是边界情况




#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<vector>

#include<queue>

#include<map>

#include<cmath>

using namespace std;

const int N = 1e5 + ;

vector<int > E[N];

int vis[N];

double p[N];

map<int, double> M;

int main() {

    int n;

    double z, r;

    cin >> n >> z;

    scanf("%lf", &r);

    r /= ;

    for (int i = ; i<n; i++) {

        int m;

        cin >> m;

        if (m == ) { double x; cin >> x; M[i] = x; continue; }//得道

        while (m--) {

            int x;

            cin >> x;

            E[i].push_back(x);

        }

    }

    //特判掉一个人的数据

    if (M.count()) { cout << (int)z*M[]; return ; }//卡样例技巧

    //找到得道者，顺便更新所有人的功力。算出ans;1.dfs到0，2.bfs

    double ans = ;

    queue<int>Q;

    Q.push(); vis[] = ; p[] = z;

    while (!Q.empty()) {

        int now = Q.front();

        Q.pop();

        for (int i = ; i<E[now].size(); i++) {

            int v = E[now][i];

            if (vis[v])continue;

            Q.push(v); vis[v] = ;

            p[v] = p[now] * (-r);//减弱r，除非得道。

            if (M.count(v)) {

                ans += p[v] * M[v]; continue;

            }

        }

    }

    int a = ans;

    printf("%d", a);

    system("pause");

}


相关文章