Total Sales of Supply Chain (2

/*
https://www.nowcoder.com/questionTerminal/6dc751a09c1f45ad84e02aa778c1e8c4
Total Sales of Supply Chain (25)   2018-12-20
General mean: Give you a A supply chain, require the total price of the last of ihis chain.
Result: Cost about 40 min, And get acpeted in first shoot. In it problm the double-type don't 
need to compared so it dont need to worry about the loss of accuracy. Both DFS and BFS is avaliable
but it is obvious that DFS can save more time. Easy problem.
*/
#include<iostream>
#include<string.h>
#include<vector>
#include<string>
using namespace std;
const int maxn = 100009;
int per[maxn];
int sell[maxn];        //more than zero if it is end of the chain
double pri[maxn];
double ans = 0.0;
int N;
double P, R;      // initial price and rate
double dfs(int p){
    int fater = per[p];
    return (pri[p] > 0 ? pri[p] : pri[p] = dfs(fater)*R);
}
int main(){
    cin >> N >> P >> R;
    R = (100 + R) / 100;
    for (int mun, next,i=0 ; i < N; i++){
        cin >> mun;
        if (mun == 0) cin>>sell[i];
        for (int j = 0; j < mun; j++){
            cin >> next;
            per[next] = i;
        }
    }
    per[0] = -1;
    pri[0] = P;
    for (int i = 0; i < N; i++){
        if (sell[i]>0) ans += sell[i] * dfs(i);
    }
    printf("%.1f\n", ans);
    return 0;
}

思路：建立数 vector<struct tree> v;中 下标 表示第几个供应商。
每个供应商有结构体中的parent 表示的父亲节点。如果parent == NULL 表示的是已经遍历到
了根节点。
题目的大意就是 其实把第一个验证以后后面的就比较方便的计算了
10(供应链的人数) 1.80(价格) 1.00(增加的百分比)
3 2 3 5 第0行表示 总共有三个供应商 2 3 5 在 0 那里拿货
1 9     第1行表示 总共有1个供应商 9 在 1 那里拿货
1 4
1 7
0 7     第4行表示 4 是一个零售商 他销售的货物总数 是7 以下 基本比较雷同
2 6 1
1 8
0 9
0 4
0 3


建立的树             0
                     |-2     3        5
                       |-4   |-7      |- 1        6
                                         |- 9     |-8
然后就可以计算了
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;

struct tree
{
    struct tree * parent;
    int data; // 存有多少货物
};


#define Debug
#ifdef Debug
ifstream ifile("case.txt");
#define cin ifile
#endif


int level = 0;
int DFS(vector<struct tree> & v, struct tree *p)
{
    if (p->parent == NULL)
        return level;
    level++;
    return DFS(v, p->parent);
}




int main()
{
    int n;
    double price, precentage;
    cin >> n >> price >> precentage;
    vector<struct tree> v(n);
    v[0].parent = NULL;
    struct tree tmp;
    for (int i = 0; i < n; i++)
    {
        int flag;
        cin >> flag;
        if (flag != 0)
        {
            int data;
            for (int j = 0; j < flag; j++)
            {
                cin >> data;
                v[data].parent = &v[i];
            }
        }
        else
        {
            // 输入货物数量
            cin >> v[i].data;
        }
    }
    // 树在这里已经建立完毕了  root 节点是 0 节点
    double sum=0;
    for(int i=0; i<n; i++)// 找出所有的叶节点然后遍历上去，虽然这个不是一个很好的方法，但是应该能做
        if (v[i].data != 0)
        {
            level = 0;
            level = DFS(v, &v[i]);
            sum += v[i].data * price * pow(1.00+precentage/100, level);
        }
    cout << fixed <<setprecision(1) << sum << endl;
    system("pause");
}

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <sstream>
using namespace std;

//1079 Total Sales of Supply Chain
//uid编号0~n-1,<10^5
//树形结构

int n;
double p, r;
int k, uid, amt;
double total_, tmp_;
const int maxn = 100005;

class node {
public:
	double price;
	int amt;
	vector<int> nxt;
	node():amt(0){}
};

node net[maxn];

int main() {
	cin >> n >> p >> r;
	net[0].price = p;


	for (int i = 0; i < n; ++i) {
		scanf("%d", &k);
		if (k == 0) {
			scanf("%d", &amt);
			net[i].amt = amt;
			continue;
		}
		for (int j = 0; j < k; ++j) {
			scanf("%d", &uid);
			net[i].nxt.push_back(uid);
		}
	}

	//跑网络
	queue<int> q;
	q.push(0);
	int cur, len, sub_;
	while (!q.empty()) {
		cur = q.front();
		q.pop();
		len = net[cur].nxt.size();
		if (len == 0) {
			tmp_ = net[cur].price*net[cur].amt;
			total_ += tmp_;
			continue;
		}
		for (int i = 0; i < len; ++i) {
			sub_ = net[cur].nxt[i];
			net[sub_].price = net[cur].price *(1 + r * 0.01);
			q.push(sub_);
		}
	}
	//保留一位小数
	cout << fixed <<setprecision(1)<< total_;

	return 0;
}

	#include <iostream>



	#include <queue>



	#include <vector>



	#include <cmath>



	usingnamespacestd;



	const int maxn=100010;



	int n,num;



	double rootprice,increase,ans=0;



	struct node{



	    double value,level;



	    vector<int> child;



	}Node[maxn];



	void layerOrder(int root){



	    queue<int> q;



	    Node[root].level=0;



	    q.push(root);



	    while(!q.empty ()){



	        int now=q.front();



	        q.pop();



	        for(int i=0;i<Node[now].child.size();i++){



	            int child=Node[now].child[i];



	            Node[child].level=Node[now].level+1;



	            q.push(child);



	        }



	        if(Node[now].child.size()==0)



	            ans+=rootprice*Node[now].value*pow(increase,Node[now].level);



	    }



	}



	int main(){



	    cin>>n>>rootprice>>increase;



	    increase=increase/100+1;



	    for(int i=0;i<n;i++){



	        int childnum;cin>>childnum;



	        if(childnum!=0){



	            for(int j=0;j<childnum;j++){



	                cin>>num;



	                Node[i].child.push_back(num);



	            }



	        }



	        else cin>>Node[i].value;



	    }



	    layerOrder(0);



	    printf("%.1f",ans);



	    return 0;



	}

//dfs爆搜即可
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n;double p,r,ans;
vector<int> G[maxn];
int sum[maxn];
void dfs(int rt,int step){
    int ok=1;
    for(int i=0;i<G[rt].size();++i){
        int v=G[rt][i];ok=0;
        dfs(v,step+1);
    }
    if(ok){
        ans+=p*pow(1+r*0.01,step)*sum[rt];    
    }    
}
int main(){
    scanf("%d %lf %lf",&n,&p,&r);
    for(int i=0,x;i<n;++i){
        scanf("%d",&x);
        if(x>0){
            for(int j=1,y;j<=x;++j)
                scanf("%d",&y),G[i].push_back(y);
        }else{
            scanf("%d",&x);
            sum[i]=x;                
        }
    }
    dfs(0,0);printf("%.1f\n",ans);    
    return 0;
} 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

int main()
{     int n;     double p,r,total=0;     cin>>n>>p>>r;     vector<int> data(n,0);     vector<int> retailer(100001,0);     for(int i=0;i<n;i++)     {         int size;         cin>>size;         if(size!=0)         {             for(int j=0;j<size;j++)             {                 int t;                 cin>>t;                 data[t] = i;             }         }else             cin>>retailer[i];     }          for(int i=0;i<n;i++)     {         if(retailer[i]!=0)         {             double y = p*retailer[i];             int m = data[i];             while(m!=0)             {                 y *= (1+r/100);                 m = data[m];             }             total += y*(1+r/100);         }     }     printf("%.1f", total);     return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int Max=1e5+10;
int n;
double p,r,ans;

struct Node {
	double data;
	vector<int> child;
} node[Max];

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);
	}
}

int main() {
	scanf("%d %lf %lf",&n,&p,&r);
	r/=100;
	for(int i=0; i<n; i++) {
		int k;
		scanf("%d",&k);
		if(k==0) scanf("%lf",&node[i].data);
		else {
			for(int j=0; j<k; j++) {
				int ch;
				scanf("%d",&ch);
				node[i].child.emplace_back(ch);
			}
		}
	}
	DFS(0,0);
	printf("%.1f\n",p*ans);
	return 0;
}

@[toc]

与这题非常类似的题目，我用的dfs解的-----Highest Price in Supply Chain

题目

OJ平台

题目翻译

• 关键句意：

where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID's of these distributors or retailers.
其中，在第i行中，Ki是从供应商i接收产品的分销商或零售商的总数，然后是这些分销商或零售商的ID。(注意i是它们的供应商！)

Kj being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj.
Kj为0意味着第j个成员是零售商，那么产品的总数量将在Kj之后给出。其实就是为0就代表它没有继续分销，直接开始零售了，接下来给出的就是他所进货的多少了。

代码详解

输入处理

void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> p >> r;
    for (int i = 0; i < N; i++) { /*建树*/
        int t; cin >> t;
        if (t)
            while (t--) {
                int n; cin >> n; //更新它的子节点
                node[i].emplace_back(n);
            }
        else { //记录结束的结点(零售商)以及它的购买数量
            int n ; cin >> n;
            mp.emplace_back(make_pair(i, n));
        }
    }
}

输出处理

先用bfs进行一次层序更新一下对应结点的增长率！再进行答案的更新。

void bfs() {
    Q.push(0); //利用bfs得出层级更新利率rr
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (auto && t : node[x]) {
            rr[t] = rr[x] + rr[x] * (r / 100.0);
            Q.push(t);
        }
    }
}
void print() {
    bfs();
    double res = 0;
    for (auto && t : mp) {
        res += rr[t.first] * (double)t.second * p;
    }
    cout << fixed << setprecision(1) << res;
}

汇总代码提交

效率不错！

#include<bits/stdc++.h>
using namespace std;
#define MaxN 100001
int N;
double p, r;
vector<int> node[MaxN];
queue<int> Q;

//这道题仍然是以0为根节点，而结束的结点它也告诉你了，在个数为0的时候作结束。
//在结点为0的时候，它最终给出它的大小(就是这条线得到的商品数量)，而销售额就是商品数量*商品价格*增长率
vector<pair<int, int>>mp;
vector<double>rr(MaxN, 1); //存储每个结点得到的增长利润
void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> p >> r;
    for (int i = 0; i < N; i++) { /*建树*/
        int t; cin >> t;
        if (t)
            while (t--) {
                int n; cin >> n; //更新它的子节点
                node[i].emplace_back(n);
            }
        else { //记录结束的结点以及它的购买数量
            int n ; cin >> n;
            mp.emplace_back(make_pair(i, n));
        }
    }
}

void bfs() {
    Q.push(0); //利用bfs得出层级更新利率rr
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (auto && t : node[x]) {
            rr[t] = rr[x] + rr[x] * (r / 100.0);
            Q.push(t);
        }
    }
}
void print() {
    bfs();
    double res = 0;
    for (auto && t : mp) {
        res += rr[t.first] * (double)t.second * p;
    }
    cout << fixed << setprecision(1) << res;
}
int main() {
    Input();
    print();
    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n;
double p,r;
vector<int> q;
vector<int> temp;
vector<vector<int>> chain;
int main(int argc, const char * argv[]) {
    cin>>n>>p>>r;
    q.push_back(0);
    int k,t;
    double price=0;
    int lay[10010];
    lay[0]=0;
    for (int i=0; i<n; i++) {
        cin>>k;
        temp.push_back(k);
        if (k!=0) {
            for (int j=0; j<k; j++) {
                cin>>t;
                temp.push_back(t);
            }
        }else{
            cin>>t;
            temp.push_back(t);
        }
        chain.push_back(temp);
        temp.clear();
    }
    while (q.size()!=0) {
        for (int i=1;i<=chain[*q.begin()][0] ; i++) {
            q.push_back(chain[*q.begin()][i]);
            lay[chain[*q.begin()][i]]=lay[*q.begin()]+1;
        }
        if (chain[*q.begin()][0]==0) {
            price+=chain[*q.begin()][1]*p*pow(1+0.01*r, lay[*q.begin()]);
        }
        q.erase(q.begin());
    }
    int p1=int(price*100)%10;
    int p2;
    if (p1<5) {
        p2=int(price*100)/10;
        price=p2/10.0;
        printf("%.1f\n", price);
    }else{
        p2=int(price*100)/10+1;
        price=p2/10.0;
        printf("%.1f\n", price);
    }
    return 0;
}

a = input().split()
c,d,m = 0,{},[]
for i in range(int(a[0])):
    b = list(map(int,input().split()))
    if b[0]:
        for j in b[1:]:
            d[j] = i
    else:
        m.append([i,b[1]])

for i in m:
    j = 0
    while i[0] in d:
        j += 1
        i[0] = d[i[0]]
    c += i[1] * float(a[1]) * (float(a[2]) / 100 + 1) ** j
        
print('{:.1f}'.format(c))

 Kj being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj.

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <iomanip>
#include <map>
using namespace std;

int main(){
    int N;
    double P, r;
    cin >> N >> P >> r;
    vector<vector<int>> chain(N);
    map<int, int> amount;
    for(int i = 0; i < N; i++){
        int k;
        cin >> k;
        if(k == 0){
            cin >> amount[i];
        }
        for(int j = 0; j < k; j++){
            int t;
            cin >> t;
            chain[i].push_back(t);
        }
    }
    queue<int> que;
    que.push(0);
    int current_level = 0, current_cnt = 1, next_cnt = 0;
    double tot = 0;
    while(!que.empty()){
        int x = que.front(); que.pop();
        if(chain[x].empty()){
            tot += amount[x] * P * pow(1 + r / 100, current_level);
        }
        else{
            for(auto d : chain[x]){
                que.push(d);
                next_cnt++;
            }
        }
        current_cnt--;
        if(current_cnt == 0){
            current_level++;
            current_cnt = next_cnt;
            next_cnt = 0;
        }
    }
    cout << fixed;
    cout << setprecision(1);
    cout << tot << endl;
}

def dfs(root,bu):
    global res
    boo = True
    for i in range(0,len(lst[root])):
        rt = lst[root][i]
        boo = False
        dfs(rt,bu+1)
    if boo:
        res+=p*pow(1+r*0.01,bu)*sa[root]
res = 0.0
n,p,r = map(float,input().split())
lst,sa,con = [],[],0
for i in range(0,int(n)):
    temp = list(map(int,input().split()))
    if temp[0]!=0:
        con+=1
        lst.append(temp[1:])
        sa.append([])
    else:
        sa.append(temp[1])
        lst.append([])
dfs(0,0)
print("%.1f"%res)

/读题一小时做题5分钟，刚开始理错误，认为不确定供应商零售商，结果尴尬的想了很久
最后发现只需要建立树即可，只要在第n行的序号就是孩子，第一个数是总数，然后建立一颗树
最后用队列进行搜索然后得出价格/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int []start;
static int []end;
static String []temp_start;
static boolean flag;
static int N;
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer;
tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
double P = Double.parseDouble(tokenizer.nextToken());
double R = Double.parseDouble(tokenizer.nextToken()) / 100 + 1;
Node[] nodes = new Node[N];
int[] child = new int[N];

    for (int i = 0; i != N; i++)
    {
        nodes[i] = new Node();
    }
    for(int i=0;i!=N;i++)
    {
        tokenizer = new StringTokenizer(reader.readLine());
        int temp = Integer.parseInt(tokenizer.nextToken());

         if (temp == 0)
        {
            child[i] = Integer.parseInt(tokenizer.nextToken());
            continue;
        }
        else if (temp >= 1)
        {

            for (int j = 0; j < temp; j++)
            {
                nodes[i].child.add(nodes[Integer.parseInt(tokenizer.nextToken())]);
            }

        }
    }

    Queue<Node> queue=new LinkedList();
    queue.add(nodes[0]);
    int next=1,count,layer=-1;
    double priceall=0;
    do {
        count=next;
        next=0;
        layer++;
        for(int j=0;j<count;j++)
        {
            Node temp =  queue.poll();
            if (!temp.child.isEmpty()) {
                next += temp.child.size();
                queue.addAll(temp.child);
            }
            else {


                int i = 0;
                for (; i < N; i++) {
                    if (nodes[i] == temp) {
                        break;
                    }
                }
                priceall+= child[i] * P * Math.pow(R, layer);
                continue;

            }

        }



    }while (next!=0);
    System.out.printf("%.1f",priceall);

}
public static class Node{
    List <Node> child;
    public Node()
    {
        child=new ArrayList<Node>();
    }

}

}

n, p, r = input().split()
n, p, r = int(n), float(p), float(r)
L = [[] for i in range(n)]
ret = [0 for i in range(n)]
for i in range(n):
    line = list(map(int, input().split()))
    if line[0] > 0:
        L[i].extend(line[1:])
    elif line[0]==0:
        ret[i] = line[1]

lev, cur, ans = 0, [0], 0.0
while cur:
    lev += 1
    now = [y for x in cur for y in L[x]]
    for t in now:
        if ret[t] > 0:
            ans += ret[t] * p * (1+r/100)**lev
    cur = now

print('%.1f' % ans)