求最长链的问题。。
这次试了下层序遍历求最大深度，感觉容易点。
#include <iostream> #include <vector> #include <queue> #define MAX 100010 using namespace std; int n; float p, r; int root; struct Node { int level; vector <int> next; Node() { level = 1; } }; Node chain[MAX]; int level[MAX]; int maxLe = 1; void levelOrder(int root) { queue <int> q; q.push(root); level[chain[root].level]++; while (!q.empty()) { int top = q.front(); q.pop(); for (int i = 0; i < chain[top].next.size(); i++) { q.push(chain[top].next[i]); chain[chain[top].next[i]].level = chain[top].level + 1; level[chain[top].level + 1]++; if (maxLe < chain[top].level + 1) { maxLe = chain[top].level + 1; } } } } int main() { cin >> n >> p >> r; int up; for (int i = 0; i < n; i++) { cin >> up; if (up == -1) { root = i; } else { chain[up].next.push_back(i); } } levelOrder(root); float sum = p; for (int i = 0; i < maxLe - 1; i++) { sum *= (1 + r / 100); } printf("%.02f %d\n", sum, level[maxLe]); return 0; }
