Highest Price in Supply Chain

 题目大意呢，有一堆商人，其中除了一个最基础的供应商，其他的都必须从上一层供应商那里拿货，只有最终的销售商才卖东西，然后让我们算最贵的销售商在哪里。

      这道题目呢，如果建模比如A从B那里拿货，你就画一条从A指向B的线，最终会构成一个图，而且所有的线最终会指向那个题目中的“root supplier”，我们的目标是在这张图中找最长路。然后注意一下保存已经搜索过的答案就好了。

      还有一个方法并是DFS搜索，反正所有的线都是从根节点开始的，我们建图的时候就不要保存某某节点的祖先是谁了，直接保存某某节点的孩子是谁把，然后从根节点开始搜索，同时保存最长距离，最后扫描一次输出。不过我没试过。

# include <cstdio>
# include <iostream>
# include <cstring>
# include <cmath>
# include <algorithm>
using namespace std;

const int _size = 100000;
int chain[_size];
int lenth[_size];
int GetLenth(int i)
{
	if (lenth[i]!=-1)
	    return lenth[i];
    if (chain[i]==-1)
        return lenth[i] = 0;
    else 
        return lenth[i] = GetLenth(chain[i]) + 1; 
}
int main()
{
  memset(lenth,-1,sizeof(lenth));
  int n;
  double p,r;
  cin >> n >> p >> r;
  for (int i=0;i<n;i++)
      cin >> chain[i];
  int Max = -1;
  for (int i=0;i<n;i++)
      Max = max(GetLenth(i),Max);
  int count = 0;
  for (int i=0;i<n;i++)
      if (lenth[i]==Max)
          count++; 
  printf("%.2lf %d\n",p*pow(1+r/100,Max),count);
  return 0;
}

#include <stdio.h>
#include <math.h>
int main(void) {
    int n, i, x;
    int max = 0, mcount = 0, count;	
    double p, r;

    static int id[100000];
    
    scanf("%d%lf%lf", &n, &p, &r);
    for (i = 0; i < n; i++) {
        scanf("%d", &id[i]);        
    }
    for (i = 0; i < n; i++) {
        x = i;
		count = 0;
        while (id[x] != -1) {
            x = id[x];
            count++;           
        }
        if (count > max) {
            max = count;
            mcount = 1;
        }
        else if (count == max) {
            mcount++;
        }                
    }
    printf("%.2f %d\n", p*pow(r/100+1, max), mcount);
    
    return 0;
}

import java.util.*;
import java.math.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        double p=sc.nextDouble();
        double r=sc.nextDouble();
        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            list.add(sc.nextInt());
        }
        int count=0;
        int depth=-1;
        for(int i=0;i<list.size();i++){
            int index=i;
            int tmpDepth=0;
            while(list.get(index)!=-1){
                index=list.get(index);
                tmpDepth++;
            }
            if(tmpDepth>depth){
                depth=tmpDepth;
                count=1;
            }else if(tmpDepth==depth){
                count++;
            }
        }
        System.out.printf("%.2f %d",p*Math.pow((100.00+r)/100,depth),count);
    }
}

//爆搜dfs
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int n,root,anscnt=0;double p,r;
vector<int> G[maxn];
map<int,int> mp;
 
void dfs(int cur,int step){
    int ok=1;
    for(int i=0;i<G[cur].size();++i){
        int v=G[cur][i];ok=0;
        dfs(v,step+1); 
    }
    if(ok){
        if(step>anscnt){
            anscnt=step;++mp[anscnt];return ;
        }
        if(step==anscnt){
            ++mp[anscnt];return ;
        }
    }
}
int main(){
    scanf("%d %lf %lf",&n,&p,&r);
    for(int i=0,tmp;i<n;++i){
        scanf("%d",&tmp);
        if(tmp==-1){ root=i;continue;}
        G[tmp].push_back(i);
    }
    dfs(root,0);    
    printf("%.2f %d\n",p*pow(1+r*0.01,anscnt),mp[anscnt]);
    return 0;
} 

不需要递归。

从每个叶子节点开始，自底向上更新高度和高度的重数。最后根节点高度的重数就是卖最高价的销售商个数。

#include <cstdio>
#include <cstdlib>
#include <cmath>

int main(){
    const int MAXN = 100100;
    int parent[MAXN], height[MAXN] = {0}, num[MAXN] = {0}; //父节点，高度，重数

    int N, root;
    double p, r;
    scanf("%d %lf %lf", &N, &p, &r);
    for(int i = 0; i < N; i ++){
        scanf("%d", parent + i);
        if(parent[i] == -1) root = i;
    }

    int nh, pos, pnt; //new height
    for(int i = 0; i < N; i ++){
        if(height[i] == 0){ //还是叶子节点
            nh = 1;
            pos = i; 
            pnt = parent[i];
            while(pnt >= 0 && height[pnt] <= nh){
                if(height[pnt] == nh){
                    num[pnt] ++; //加一重
                }else{
                    height[pnt] = nh; //更新高度
                    num[pnt] = 1; //只有一重
                }
                pos = pnt;
                pnt = parent[pnt];
                nh ++;
            }
        }
    }

    double hp = p * pow(1 + r / 100, height[root]);
    printf("%.2lf %d", hp, num[root]);

    return 0;
}

#include <iostream>
#include <math.h>
using namespace std;
//使用递归调用找到root supply
void findsupply(int mb[],int i,int *time){
    if(mb[i]!=-1){
        *time = *time +1;
        findsupply(mb,mb[i],time);
    }
    else return;
}
int main(){
    int N;
    double P=0,R=0;
    cin>>N>>P>>R;
    int members[N];
    for (int i=0;i<N;i++){
        cin>>members[i];
    }
    int maxtime=0;
    int time = 0;
    int tarry[N];
    for (int i=0;i<N;i++){
        findsupply(members,i,&time);
        if(time >maxtime)
            maxtime = time;
        tarry[i]= time;
        time = 0;
    }
    int n=0;
    for (int i=0; i<N; i++) {
        if (maxtime==tarry[i])
            n++;
    }
    printf("%.2f %d",P*pow(R/100+1, maxtime),n);

	}



	//递归

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {//注意while处理多个case
        	int n = in.nextInt();//the total number of the members in the supply chain （供应链）
        	double p = in.nextDouble();//the price given by the root supplier;
        	double r = in.nextDouble()/100;//每个零售商或经销商的价格增长率
        	Node[] nodes = new Node[n];
        	Node root = null;
        	for(int i = 0;i<n;i++){
        		int parent = in.nextInt();
        		nodes[i] = new Node(parent);
        		if(parent==-1)
        			root = nodes[i];
        	}
        	for(int i = 0;i<n;i++){
        		if(nodes[i].parent!=-1){
        			nodes[nodes[i].parent].addChild(nodes[i]);
        		}
        	}
        	int d = -1;
        	int retailers = 0;
        	Queue<Node> queue = new LinkedList<Node>();
        	queue.add(root);
        	while(!queue.isEmpty()){
        		d++;
        		int size = queue.size();
        		retailers = size;
        		while(size--!=0){
        			Node top = queue.poll();
            		for(int i = 0;i<top.count;i++){
            			queue.add(top.getChild(i));
            		}
        		}
        	}
        	p *= Math.pow(1+r, d);
        	System.out.printf("%.2f %d\n",p,retailers);
        }
    }
    private static class Node{
    	int parent;
    	int count;
    	ArrayList<Node> children;
		public Node(int parent) {
			this.parent = parent;
			this.children = new ArrayList<Node>();
		}
		public void addChild(Node node){
			children.add(node);
			count++;
		}
		public Node getChild(int i){
			if(i>=children.size())
				return null;
			return children.get(i);
		}
    }
}

#include<iostream>
(720)#include <vector>
#include <map>
(747)#include <algorithm>

using namespace std;

map<int, vector<int>> dealer_hash;
int max_depth = 0;

bool is_leafnode(int index)
{
	if (dealer_hash.find(index) == dealer_hash.end())
		return true;
	return false;
}

vector<pair<int, int>> leaf_node;

void bfs(int index, int deep)
{
	if (is_leafnode(index))
	{
		leaf_node.push_back({ index, deep });
		max_depth = max(max_depth, deep);
	}
	else
	{
		vector<int> v = dealer_hash[index];
		for (auto idx : v)
			bfs(idx, deep + 1);
	}
}

int main()
{
	int n;
	double p, r;
	cin >> n >> p >> r;
	for (int i = 0; i < n; i++)
	{
		int x; cin >> x;
		dealer_hash[x].push_back(i);
	}
	bfs(-1, -1);
	int cnt = 0;
	for (auto leaf : leaf_node)
	{
		//printf("leaf=%d deep=%d\n", leaf.first, leaf.second);
		if (leaf.second == max_depth)
			cnt++;
	}
	while (max_depth != 0)
	{
		p *= (r + 100) / 100;
		max_depth--;
	}
	printf("%.2f %d\n", p, cnt);
}

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=100010;
int n,num,root,maxlevel=0,maxnum=0;
double rootprice,increase;
vector<int> Node[maxn];             //存放树
void DFS(int now,int level){
    if(Node[now].size()==0){        //当前为叶结点
        if(level>maxlevel){
            maxlevel=level;
            maxnum=1;
        }
        else if(level==maxlevel)
            maxnum++;
    }
    for(int i=0;i<Node[now].size();i++)  //递归访问结点now的字结点
        DFS(Node[now][i],level+1);
    }
int main(){
    cin>>n>>rootprice>>increase;
    increase=increase/100+1;
    for(int i=0;i<n;i++){
        cin>>num;
        if(num==-1) root=i;             //根结点无父结点
        else Node[num].push_back(i);
    }
    DFS(root,0);
    printf("%.2f %d",rootprice*pow(increase,maxlevel),maxnum);
    return 0;
} 

try:
    while True:
        n,p,r = list(map(float,input().split()))
        nodes = list(map(int,input().split()))
        result = []
        for node in nodes:
            index = 0
            while node != -1:
                index += 1
                node = nodes[node]
            result.append(round(p*(r/100+1)**index,2))
        print('%.2f %d'%(max(result),result.count(max(result))))
except Exception:
    pass

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

using namespace std;

int main()
{     int n,x,Max=0,max_cnt=0,cnt,a[100010];     double p,r;     cin>>n>>p>>r;     for(int i=0;i<n;i++)         cin>>a[i];     for(int i=0;i<n;i++)     {         x = i;         cnt = 0;         while(a[x] != -1)         {             x = a[x];             cnt++;         }         if(cnt > Max)         {             Max = cnt;             max_cnt = 1;         }else if(cnt == Max)             max_cnt++;     }     printf("%.2f %d\n", p*pow(1+r/100, Max), max_cnt);     return 0;
}

	

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

const int Max=1e5+10;
vector<int> child[Max];
int n,maxdepth,num;
double p,r;

void DFS(int index,int depth) {
	if(child[index].size()==0) {
		if(depth>maxdepth) {
			maxdepth=depth;
			num=1;
		} else if(depth==maxdepth) {
			num++;
		}
		return ;
	}
	for(int i=0; i<child[index].size(); i++) {
		DFS(child[index][i],depth+1);
	}
}

int main() {
	int father,root;
	scanf("%d %lf %lf",&n,&p,&r);
	r/=100;
	for(int i=0; i<n; i++) {
		scanf("%d",&father);
		if(father==-1) root=i;
		else child[father].emplace_back(i);
	}
	DFS(root,0);
	printf("%.2f %d\n",p*pow(1+r,maxdepth),num);
	return 0;
}

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

struct node{  //tree node for forest
	int name;
	node* head;
};

int main(){
	int n;
	double price, rate;
	cin>>n>>price>>rate;
	vector<int> data(n);
	int temp,temp2;
	node* root;
	root=new node;
	root->name=-1;
	root->head=NULL;
	for(int i=0;i<n;i++){
		cin>>data[i];
	}
	vector<node*> node_list(n);
	node* tp;
	for(int i=0;i<n;i++){
		tp=new node;
		tp->name=i;
		node_list[i]=tp;
	}
	for(int i=0;i<n;i++){
		if(data[i]!=-1){
			tp=node_list[i];
			temp2=data[i];
			tp->head=node_list[temp2];
		}
		else{
			tp=node_list[i];//must use tempo variable to get the data from vector 
			tp->head=root;
		}
	}
	int len;int max_len=0;int max_len_pos=0;int total_count=0;
	for(int i=0;i<n;i++){
		tp=node_list[i];
		len=0;
		while(tp->head!=NULL){
			//cout<<tp->name<<" ";//
			tp=tp->head;
			len++;
		}
		if(len>max_len){
			max_len=len;
			max_len_pos=i;
			total_count=1;
		}
		else if(len==max_len)total_count++;
		//cout<<len<<" "<<max_len<<" "<<max_len_pos<<endl;//
	}
	double highest_price=price*pow(rate/100+1, max_len-1);
	cout<<fixed<<setprecision(2)<<highest_price;
	cout<<" ";
	cout<<total_count;
//	cout<<endl<<max_len;
	return 0;
}

#include<cstdio>
#include<vector>
using namespace std;
double ans=0,inf=-1,rate,price;
int n,root=0,u,cnt=0;
vector<int> tree[100010];
void dfs(int root,double pri){
	if(tree[root].size()==0){
		if(pri>inf) 
			inf=pri,cnt=1;
		else if(pri == inf) cnt++;
		return ;
	}
	for(int i=0;i<tree[root].size();i++)
		dfs(tree[root][i],pri*(1+rate));
}
int main(){
	scanf("%d%lf%lf",&n, &price, &rate);
	rate/=100;
	for(int i=0;i<n;i++){
		scanf("%d", &u);
		if(u==-1) root=i;
		else tree[u].push_back(i);
	}
	dfs(root,price);
	printf("%.2f %d",inf,cnt);
	return 0;
}