Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti. The weight of a path from R to L is defined to be the sum of the weights of all the nodes along the path from R to any leaf node L.
Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let's consider the tree showed in Figure 1: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in Figure 1.
Figure 1Input Specification:
Each input file contains one test case. Each case starts with a line containing 0 < N <= 100, the number of nodes in a tree, M (< N), the number of non-leaf nodes, and 0 < S < 230, the given weight number. The next line contains N positive numbers where Wi (<1000) corresponds to the tree node Ti. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID's of its children. For the sake of simplicity, let us fix the root ID to be 00.
Output Specification:
For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.
Note: sequence {A1, A2, ..., An} is said to be greater than sequence {B1, B2, ..., Bm} if there exists 1 <= k < min{n, m} such that Ai = Bifor i=1, ... k, and Ak+1 > Bk+1.
Sample Input: 20 9 24 10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2 00 4 01 02 03 04 02 1 05 04 2 06 07 03 3 11 12 13 06 1 09 07 2 08 10 16 1 15 13 3 14 16 17 17 2 18 19 Sample Output: 10 5 2 7 10 4 10 10 3 3 6 2 10 3 3 6 2 题目： 建立一棵树，给定一个路径代价大小，输出所有的代价等于该给定代价的路径（根到叶子） 思路&&解法： parent指针建树，建好之后从每一个叶子结点网上算出到根的代价，等于就保存 这题比较烦的是输出需要按升序，也就是需要多关键字比较 比较的方法：每一个符合条件的路径都保存在一个vector《int》里面，所有的路径保存在一个更大的vector《vector《int》》里面 用sort函数实现多关键字排序，cmp函数需要自定义 注：sort排序崩溃，要检查cmp函数是不是有越界的情况 Code： #include <iostream> #include <vector> #include <algorithm> #include <stdio.h> #include <math.h> #define MAXN 101 struct TreeNode { int value; TreeNode * parent; int weight; }; bool cmp(std::vector<int> a, std::vector<int> b) { // 多关键字vector排序 int size = a.size() < b.size() ? a.size() : b.size(); int mark = 0; while (mark < size-1 && a[mark] == b[mark]) { mark++; } return a[mark] > b[mark]; } int main() { int num_nodes, num_unleaves, given_weight; std::vector<int> leaves; scanf("%d %d %d", &num_nodes, &num_unleaves, &given_weight); TreeNode* nodes[MAXN]; bool is_leave[MAXN]; std::vector<int> route[MAXN]; std::fill(is_leave, is_leave + MAXN, true); for (int i = 0; i < num_nodes; i++) { nodes[i] = (TreeNode*)malloc(sizeof(TreeNode)); nodes[i]->parent = NULL; int weight; std::cin >> weight; nodes[i]->weight = weight; } for (int i = 0; i < num_unleaves; i++) { int non_leaves; int k; std::cin >> non_leaves; is_leave[non_leaves] = false; std::cin >> k; while (k--) { int child; std::cin >> child; nodes[child]->parent = nodes[non_leaves]; } } std::vector<int> output_leaves; for (int i = num_nodes - 1; i >= 0; i--) { if (is_leave[i]) { int cost = 0; TreeNode* p = nodes[i]; while (p) { cost += p->weight; route[i].insert(route[i].begin(), p->weight); p = p->parent; } if (cost == given_weight) { output_leaves.push_back(i); } } } std::vector< std::vector<int> > output_element; for (int i = 0; i < output_leaves.size(); i++) { output_element.push_back(route[output_leaves[i]]); } sort(output_element.begin(), output_element.end(), cmp); for (int i = 0; i < output_element.size(); i++) { for (int j = 0; j < output_element[i].size()-1; j++) { printf("%d ", output_element[i][j]); } printf("%d\n", output_element[i].back()); } system("pause"); }