一、题目描述

原题链接

Input Specification:

​​Output Specification:

Sample Input:

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

Sample Output:

1.8362 2

二、解题思路

供应链类型的dfs题目在之前已经遇见过两次，这道题的答案也非常类似，利用简单的dfs更新价格即可。

三、AC代码

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int maxn = 100010; double minp = 10000000010.0; int cnt = 0; //记录最低价的零售商个数 double pr, r; //价格，涨幅 struct Supply { double price; vector<int> chain; }sup[maxn]; void dfs(int root) //深度优先搜索 { if(sup[root].chain.size() == 0) //如果搜索到的是零售商，判断是不是最低价格 { if(sup[root].price < minp) { minp = sup[root].price; cnt = 0; cnt++; } else if(sup[root].price == minp) cnt++; } else //否则更新它供应链下一级的价格 { for(int i=0; i<sup[root].chain.size(); i++) sup[sup[root].chain[i]].price = sup[root].price * r; for(int i=0; i<sup[root].chain.size(); i++) dfs(sup[root].chain[i]); } } int main() { int N, num, tmp; scanf("%d%lf%lf", &N, &pr, &r); r = 1 + r/100; sup[0].price = pr; for(int i=0; i<N; i++) { scanf("%d", &num); for(int j=0; j<num; j++) { scanf("%d", &tmp); sup[i].chain.push_back(tmp); } } dfs(0); //起点 printf("%.4f %d", minp, cnt); return 0; }