【1079】Total Sales of Supply Chain (25 分)

1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805388447170560
给出一棵树，求出叶子结点“带权路径”之和，这里不是以前那种带权，叶子结点真正的权值由该结点的深度决定（幂次方）——根结点处货物的价格为P，叶子结点的括号内数字表示货物数。
看懂题目的输入，每行开头为当前结点i的叶子结点个数，若该首数字非0，则该行后面的数字都为i结点的叶子结点数组下标（也就是题目直接给出结点的编号，且结点的编号一定是0、1、…N-1，N为结点个数——不需要newNode函数，因为题目中给定的编号可以直接作为Node数组的下标使用）；而若该首数字为0，则该行后面的数字为叶结点的权值。

2.思路

DFS就对了，注意这题根结点的深度应设为0。

void DFS(int index,int depth){
	if(Node[index].child.size()==0){//到达叶结点
		ans+=Node[index].data*pow(1+r,depth);
		return;
	}
	for(int i=0;i<Node[index].child.size();i++){
		DFS(Node[index].child[i],depth+1);
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

3.完整代码

#include<vector>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cmath>
using namespace std;
const int maxn=100010;
double ans=0,rate;
struct node{
	double data;
	vector<int> child;
}Node[maxn];
void DFS(int index,int depth){
	if(Node[index].child.size()==0){
		ans+=Node[index].data*pow(1+rate,depth);
		return;
	}
	for(int i=0;i<Node[index].child.size();i++){
		DFS(Node[index].child[i],depth+1);//递归访问子结点
	}
}
int main(){
	int n;
	int num;
	double price;
	scanf("%d%lf%lf",&n,&price,&rate);
	rate/=100;
	for(int i=0;i<n;i++){
		scanf("%d",&num);
		if(num==0){
			scanf("%lf",&Node[i].data);
		}else{
			for(int j=0;j<num;j++){
				//scanf("%d",&Node[i].child[j]);
				int child;
				scanf("%d",&child);
				Node[i].child.push_back(child);
			}
		}
	}
	DFS(0,0);
	printf("%.1f\n",price*ans);
	system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

4.注意

（1）一开始OJ提示答案错误，后来发现是定义了全局变量rate后，还在main函数里面重复定义了rate局部变量。
（2）注意scanf("%d",&Node[i].child[j])这样写不对。
（3）题目给定的rate是百分数，因此要除以100，如样例的rate=1.00指1%。

【1090】Highest Price in Supply Chain (25 分)

1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805376476626944

2.思路

和上一题类似，区别是这个要求所有叶结点中的最高价格（每层的货物价格会在父结点的价格上增加r%）和这个价格的叶结点总个数，也即【1090】的叶子结点的“初始”点权值是相同的，即只要计算深度最深的结点。
由于不用考虑结点的点权，可以不用设结构体结点了，而直接用vector<int>child[MAXV]替代，每个child[i]都是一个vector，存放各个结点的所有子结点下标。

3.完整代码

#include<vector>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cmath>
using namespace std;
const int maxn=100010;
int num=0;//最大深度的结点个数
vector<int>child[maxn];
int maxdepth=0;
double ans;
double rate,price;
void DFS(int index,int depth){
	if(child[index].size()==0){
		if(depth>maxdepth){//递归边界：到达叶结点
			maxdepth=depth;
			ans=price*pow(1+rate,maxdepth);
			//printf("%lf\n",price);
			num=1;//重置最大深度的结点个数为1
		}else if(depth==maxdepth){
			num++;
			ans=price*pow(1+rate,maxdepth);//别漏了这句
		}
		return;
	}
	for(int i=0;i<child[index].size();i++){//注意判断的下标不是i
		DFS(child[index][i],depth+1);
	}
}
int main(){
	int n,father,root;
	scanf("%d%lf%lf",&n,&price,&rate);
	rate/=100;
	for(int i=0;i<n;i++){
		scanf("%d",&father);
		if(father!=-1)
			//child[father][i]=i;
			child[father].push_back(i);//i是father的子结点
		else
			root=i;
	}
	DFS(root,0);
	printf("%.2f %d\n",ans,num);
	system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

4.注意

（1）根结点显然没有父结点，所以输入的第二行中遇到-1时的i即为root。
（2）题目给定的rate是百分数，因此要除以100，如样例的rate=1.00指1%。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112731003