Total Sales of Supply Chain"/>
PAT1079 Total Sales of Supply Chain
<pre name="code" class="cpp">
#include<stdio.h>
#include<string.h>
#include<math.h>
#include <iostream>
using namespace std;
int Father[100000];
int depth[100000];
int volume[100000];//若为-1,则代表是一个根节点,若为非负数,则代表i是一个retailer,数组记录的是retailer的销量
int finddepth(int x){if (depth[x]==-1) {depth[x]=finddepth(Father[x])+1;}return depth[x];
}
int main(){int n;double p,r,sum=0;int k;int total;int child;memset(depth, 0xff, sizeof(depth));memset(volume, 0xff, sizeof(volume));memset(Father, 0, sizeof(Father));depth[0]=0;// freopen("/Users/pantingting/Documents/code/data/input", "r", stdin);scanf("%d%lf%lf",&n,&p,&r);for (int i=0; i<n; i++) {scanf("%d",&k);if (k==0) {//如果是retailer则记录销量scanf("%d",&total);volume[i]=total;}for (int j=0; j<k; j++) {//如果是非叶节点则建树。scanf("%d",&child);Father[child]=i;}}for (int i=0; i<n; i++) {if (volume[i]!=-1) {//如果是非负节点则计算sumsum+=volume[i]*p*pow(1+r/100.00, finddepth(i));}}printf("%.1lf\n",sum);return 0;
}
经学弟点拨,优化了了寻找深度的算法,将复杂度降了下来,全部case通过了。
更多推荐
PAT1079 Total Sales of Supply Chain
发布评论