【1106】Lowest Price in Supply Chain (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//key:在A1079基础上多个全局变量num记录深度最小的叶结点个数

const int maxn=100010;
const double INF=1e12; //很大的数,10^12
vector<int> Node[maxn]; //Node[i]存放i的所有孩子结点的编号
int n,num=0;  //n为结点个数，num为价格最低的叶子结点个数
double p,r,ans=INF; //ans为最低叶子结点价格
void DFS(int index,int depth){
	if(Node[index].size() == 0) { //到达叶结点
		double price=p*pow(1+r,depth);  //当前价格，每个都先算好
		if(price<ans){  //如果低于最低全局价格
			ans=price; //更新全局最低价格
			num=1;  //价格最低的叶子结点个数加1
		}else if(price == ans ){  //如果等于全局最低价格
			num++;  //价格最低的叶结点个数加1(最后要输出这类结点个数！)
		}
		return ;
	}
	for(int i=0;i<Node[index].size();i++){  
		DFS(Node[index][i], depth+1);  //递归访问子结点
	}
}
int main(){   
	int k,child;
	scanf("%d%lf%lf",&n,&p,&r); 
	r/=100;
	for(int i=0;i<n;i++){
		scanf("%d",&k);
		if(k!=0){  //叶结点标志,和1079不同，这里不用考虑k==0情况
			for(int j=0;j<k;j++){ 
				scanf("%d",&child);
				Node[i].push_back(child); //child为结点i的子结点
			}
		}
	}
	DFS(0,0); //根结点深度设为0！！
	printf("%.4f %d\n",ans,num);  //输出结果
	system("pause");
    return 0;   
}

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

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