1079 Total Sales of Supply Chain (25 分) DFS

2023-10-09 11:48
文章标签 25 dfs chain 1079 total sales supply

本文主要是介绍1079 Total Sales of Supply Chain (25 分) DFS,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A supply chain is a network of retailers(零售商), distributors(经销商), and suppliers(供应商)-- everyone involved in moving a product from supplier to customer.

Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.

Now given a supply chain, you are supposed to tell the total sales from all the retailers.

Input Specification:

Each input file contains one test case. For each case, the first line contains three positive numbers: N (≤10^5), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N−1, and the root supplier’s ID is 0); P, the unit price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:

Ki ID[1] ID[2] ... ID[Ki]

where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. K​j being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the total sales we can expect from all the retailers, accurate up to 1 decimal place. It is guaranteed that the number will not exceed 10^10
​​ .

Sample Input:

10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3

Sample Output:

42.4

题意:给出树的总的结点的个数,和商品的起始单价,和经过每一层要涨的比例r,从根节点开始往下走,每层的价格都是父亲结点价格的(1+r%)倍,并且在输入的时候如果k等于0的话,就说明输入的是当前结点的值,题目给出了所有叶子结点的值,求他们的价格之和。
思路:不要被零售商,经销商,供应商这三者之间的关系弄乱了,其实就是算每个叶子结点在树的第几层即可,用dfs来把层数算好,把结点的子节点都遍历过去,算出结果。

#include<iostream>
#include<cstdio>
#include<stack> 
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<map>using namespace std;double p,r;
double ans = 0.0;struct node {double data;vector<int> child;
};vector<node> v;void dfs(int index,int depth) {if(v[index].child.size() == 0) {ans = ans + v[index].data * pow(1 + r,depth);} for(int i = 0;i < v[index].child.size();i++) {dfs(v[index].child[i],depth + 1);}
}int main() {int n,k,x,c;scanf("%d%lf%lf",&n,&p,&r);r = r / 100;v.resize(n);for(int i = 0;i < n;i++) {scanf("%d",&k);if(k == 0) {scanf("%lf",&v[i].data);} else {for(int j = 0;j < k;j++) {scanf("%d",&x);v[i].child.push_back(x);}}}dfs(0,0);printf("%.1lf",ans * p);return 0;
} 

这篇关于1079 Total Sales of Supply Chain (25 分) DFS的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/172636

相关文章

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

【JavaScript】LeetCode:21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心:连续和(count)< 0时,放弃当前起点的连续和,将下一个数作为新起点,这里提供使用贪心算法解决本题的代码。动态规划:dp[i]:以nums[i]为结尾的最长连续子序列(子数组)和。 dp[i] = max(dp[i - 1]

Keysight U8031A DC power supply

Keysight U8031A DC power supply 文章目录 Keysight U8031A DC power supply前言电容充电⽰意图一、恒定电压操作二、恒定电流操作三、5v操作四、跟踪模式操作五、存储器操作六、对过电压保护编程七、对过电流保护编程八、锁键操作 前言 U8031A Power Supply 是一款具备前面板编程能力的三路输出电源。通过使

nyoj99(并查集+欧拉路+dfs)

单词拼接 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 5 描述 给你一些单词,请你判断能否把它们首尾串起来串成一串。 前一个单词的结尾应该与下一个单词的道字母相同。 如 aloha dog arachnid gopher tiger rat   可以拼接成:aloha.arachnid.dog.gopher.rat.tiger 输入 第一行是一个整

【CF】E. Anya and Cubes(双向DFS)

根据题意的话每次递归分3种情况 一共最多25个数,时间复杂度为3^25,太大了 我们可以分2次求解第一次求一半的结果,也就是25/2 = 12,记录结果 之后利用剩余的一半求结果 s-结果 = 之前记录过的结果 就可以 时间复杂度降低为 3 ^ (n/2+1) 题目链接:http://codeforces.com/contest/525/problem/E #include<set

2025年25届计算机毕业设计:如何实现高校实验室Java SpringBoot教学管理系统

✍✍计算机毕业编程指导师** ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java、Python、微信小程序、大数据实战项目集 ⚡⚡文末获取源码 文章目录 ⚡⚡文末获取源码高校实验室教学管理系统-研究背景高校实验室教学管理系