PAT1090 Highest Price in Supply Chain (25 分) 1079Total Sales of Supply Chain (25 分)

使用向量數組，将父結點相同的結點下标存在同一個向量中，也即結點i的子結點的下标都存在parentNode[i]中。本質上還是樹的層次周遊。(改叫child可能更合适，child[i]表示結點i的所有子結點的下标)。

方法一：BFS

#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 100005

int N;
double P, r;
vector<int> parentNode[MAXN];//parentNode[i]存放父結點下标為i的結點的下标
int rootIndex;

struct node{
//    int parentIndex;
    int layer;
}Nodes[MAXN];

int layerOrder(int &maxLayerCount){
    int maxLayer = 1;
    
    queue<int> q;
    Nodes[rootIndex].layer = 1;
    q.push(rootIndex);
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        for (int i=0; i<parentNode[top].size(); i++) {
            int nowLayer = Nodes[top].layer + 1;
            Nodes[parentNode[top][i]].layer = nowLayer;
            q.push(parentNode[top][i]);
            
            if (nowLayer == maxLayer) {
                maxLayerCount++;
            }
            if (nowLayer > maxLayer) {
                maxLayer = nowLayer;
                maxLayerCount = 1;
            }
        }
    }
    
    return maxLayer;
}

int main(int argc, const char * argv[]) {
    scanf("%d %lf %lf", &N, &P, &r);
    for (int i=0; i<N; i++) {
        int num;
        scanf("%d", &num);
//        Nodes[i].parentIndex = num;
        if (num == -1) {
            rootIndex = i;
        }else{
            parentNode[num].push_back(i);
        }
    }
    
    int maxLayerCount = 0;
    int maxLayer = layerOrder(maxLayerCount);
    double highest = P * pow(1 + r/100, maxLayer - 1);
    
    printf("%.2f %d", highest, maxLayerCount);
    return 0;
}


//9 1.80 1.00 1 5 4 4 -1 4 5 3 6
//1.85 2
           

方法二：DFS

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
#define MAXN 100005

int N;
double P, r;
vector<int> child[MAXN];//child[i]存放結點下标為i的所有子結點的下标
int rootIndex;

struct node{
    int layer;
//    vector<int> child;
}Nodes[MAXN];

int maxLayer = 0;
int maxLayerCount = 0;
void DFS(int index, int layer){
    if (child[index].size() == 0) {
        if (Nodes[index].layer == maxLayer) {
            maxLayerCount++;
            return;
        }
        if (Nodes[index].layer > maxLayer) {
            maxLayer = Nodes[index].layer;
            maxLayerCount = 1;
            return;
        }
    }
    
    for (int i=0; i<child[index].size(); i++) {
        Nodes[child[index][i]].layer = layer + 1;
        DFS(child[index][i], layer+1);
    }
}

int main(){
    scanf("%d %lf %lf", &N, &P, &r);
    r /= 100;
    for (int i=0; i<N; i++) {
        int parent;
        scanf("%d", &parent);
        if (parent == -1) {
            rootIndex = i;
        }else{
            child[parent].push_back(i);
        }
    }
    
    Nodes[rootIndex].layer = 1;
    DFS(rootIndex, 1);//遞歸調用注意初始參數，不要想當然。本題根結點下标就不是0，而是rootIndex。
    
    double highest = P * pow(1+r, maxLayer-1);
    printf("%.2f %d", highest, maxLayerCount);
    return 0;
}
           

BFS得24分，DFS得25分。最近再遇到兩種方法都能用的題目，多練練DFS。

1079

1.送出之前要記得把調試用的輸出中間結果的代碼注釋掉！！測試的時候就在末尾加上//，防止後來沒看到。

2.了解上不太确定的地方讀題的時候就可以記下來。比如起先用layer-2答案比樣例給的小一點點，因為r是百分之1，是以想到可能是(1+r)多乘一次少乘一次的問題，改成layer-1就對了。

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 100005

int N;
double P, r;

struct node{
    vector<int> child;
    int products = 0;//有自動初始化為0
    int layer;
}Nodes[MAXN];

int retailers[MAXN];
int retailerCount = 0;

//void Init(){
//    for (int i=0; i<N; i++) {
//        Nodes[i].products = 0;
//    }
//}

void layerOrder(){
    Nodes[0].layer = 1;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        for (int i=0; i<Nodes[top].child.size(); i++) {
            int child = Nodes[top].child[i];
            Nodes[child].layer = Nodes[top].layer + 1;
            q.push(child);
        }
        
    }
    
}

int main(int argc, const char * argv[]) {
    scanf("%d %lf %lf", &N, &P, &r);
    r = r / 100;
    for (int i=0; i<N; i++) {
        int num;
        scanf("%d", &num);
        if (num == 0) {
            scanf("%d", &Nodes[i].products);
            retailers[retailerCount++] = i;
        }else{
            for (int j=0; j<num; j++) {
                int childNum;
                scanf("%d", &childNum);
                Nodes[i].child.push_back(childNum);
            }
        }
    }
    
    //set the layer of all the nodes
    layerOrder();
    
    
    double sales = 0;
    for (int i=0; i<retailerCount; i++) {
        double temp = P * (pow(1 + r, Nodes[retailers[i]].layer - 1)) * Nodes[retailers[i]].products;//layer - 2 -> layer - 1
        // printf("%d temp = %.2f\n", retailers[i], temp);
        sales += temp;
    }
    printf("%.1f", sales);
    
    return 0;
}


//10 1.80 1.00
//3 2 3 5
//1 9
//1 4
//1 7
//0 7
//2 6 1
//1 8
//0 9
//0 4
//0 3
//
//42.4