1106 Lowest Price in Supply Chain (25 分)

题目大意

提供一棵树，在树根处货物的价格为p，从根结点开始每往下一层，该层货物价格将会在父亲结点的价格上增加r%。求叶子结点出能获得的最低价格以及能提供最低价格的叶子结点数

基本思路

数据结构：
定义vector v[maxn]，下标为结点编号，值为这个结点所有孩子结点的编号。
定义数组book，下标为层次，值为该层的叶子结点的数量。
基本思路：
dfs深搜求出拥有每一层叶子结点的数量。
求出拥有叶子结点的最小层号和该层的叶子结点数量。
按要求计算，输出。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=100005;
int n;//结点数量（结点编号0~n-1，规定编号0为根结点）
double p,r;
int book[maxn]={0};//下标为层次，值为该层的叶子结点的数量
vector<int> v[maxn];//下标为结点编号，值为这个结点所有孩子结点的编号
void dfs(int root,int depth){if(v[root].size()==0){book[depth]++;return;}for(int i=0;i<v[root].size();i++){dfs(v[root][i],depth+1);}
}
int main(){cin>>n>>p>>r;//构建这张无环有向图：读入所有结点的孩子结点编号int k,ans;for(int i=0;i<n;i++){cin>>k;for(int j=0;j<k;j++){cin>>ans;v[i].push_back(ans);}}//dfs深搜给数组book赋值dfs(0,1);//从根结点编号0，第1层开始dfs//找出存在叶子结点的最小层号，该层的结点数量int mindepth=1,num=0;//存在叶子结点的最小层号，该层的结点数量while(book[mindepth]==0) mindepth++;num=book[mindepth];//输出printf("%.4lf %d",pow((1+r*0.01),mindepth-1)*p,num);
}

类似题目

1090 Highest Price in Supply Chain (25 分)

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=100005;
int n;//结点数量（结点编号0~n-1）
double p,r;
vector<int> v[maxn];//下标为结点编号，值为这个结点所有孩子结点的编号
int root;//根结点编号（待定）
int book[maxn]={0};//下标为层号，值为该层的叶子结点的数量
void dfs(int root,int depth){if(v[root].size()==0){book[depth]++;return;}for(int i=0;i<v[root].size();i++){dfs(v[root][i],depth+1);}
}
int main(){cin>>n>>p>>r;//构建这张无环有向图：读入所有结点的孩子结点编号int ans;for(int i=0;i<n;i++){cin>>ans;if(ans==-1){root=i;}else{v[ans].push_back(i);}}//dfs深搜求出这张图的最大层次和最大层次上的结点编号dfs(root,1);//从根结点编号root，第1层开始dfs//找出存在叶子结点的最大层号，该层的结点数量int maxdepth=n,num=0;//存在叶子结点的最大层号，该层的结点数量while(book[maxdepth]==0) maxdepth--;num=book[maxdepth];//输出printf("%.2lf %d",pow((1+r*0.01),maxdepth-1)*p,num);
}

类似题目

1079 Total Sales of Supply Chain (25 分)

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=100005;
int n;//结点数量（结点编号0~n-1，规定编号0为根结点）
double p,r;
vector<int> book[maxn];//下标为层次，值为该层的所有叶子结点的编号
int productnum[maxn];//下标为结点编号，值为该零售点产品的数量
vector<int> v[maxn];//邻接表，下标为结点编号，值为这个结点所有孩子结点的编号
void dfs(int root,int depth){if(v[root].size()==0){book[depth].push_back(root);return;}for(int i=0;i<v[root].size();i++){dfs(v[root][i],depth+1);}
}
int main(){cin>>n>>p>>r;//构建这张无环有向图：读入所有结点的孩子结点编号//如果当前结点为零售点，读入零售点的产品数量int k,ans;for(int i=0;i<n;i++){cin>>k;if(k==0) cin>>productnum[i];for(int j=0;j<k;j++){cin>>ans;v[i].push_back(ans);}}//dfs深搜给数组book赋值dfs(0,1);//从根结点编号0，第1层开始dfs//找出存在叶子结点的最小层号，存在叶子结点的最大层号int mindepth=1,maxdepth=n;//存在叶子结点的最小层号，存在叶子结点的最大层号while(book[mindepth].size()==0) mindepth++;while(book[maxdepth].size()==0) maxdepth--;//求总的销售额double result=0.0;for(int i=mindepth;i<=maxdepth;i++){for(int j=0;j<book[i].size();j++){result+=pow((1+r*0.01),i-1)*p*productnum[book[i][j]];}}//输出printf("%.1lf",result);
}