PTA A_1053 Path of Equal Weight

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805424153280512

解：
多叉树遍历

1. #include<cstdio>
   
2. #include<vector>
   
3. #include<algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. typedef struct node{
   
8.     int weight;
   
9.     vector<int> children;
   
10. } BTNode;
    
11. 
    
12. BTNode tree[105];
    
13. int total = 0, s;
    
14. vector<int> path;
    
15. vector< vector<int> > ans;
    
16. 
    
17. void pretorder(int root)
    
18. {
    
19.     int w = tree[root].weight, l = tree[root].children.size();
    
20. 
    
21.     path.push_back(w);
    
22.     if ((total += w) == s && !l) ans.push_back(path);
    
23. 
    
24.     for (int i = 0; i < l; i++)
    
25.         pretorder(tree[root].children[i]);
    
26. 
    
27.     path.pop_back();
    
28.     total -= w;
    
29. }
    
30. 
    
31. bool cmp(vector<int> a, vector<int> b)
    
32. {
    
33.     return a > b;
    
34. }
    
35. 
    
36. int main(void)
    
37. {
    
38.     int n, m;
    
39.     scanf("%d %d %d", &n, &m, &s);
    
40.     if (!n) return 0;
    
41. 
    
42.     for (int i = 0; i < n; i++)
    
43.         scanf("%d", &tree[i].weight);
    
44. 
    
45.     while (m--)
    
46.     {
    
47.         int id, k;
    
48. 
    
49.         scanf("%d %d", &id, &k);  
    
50.         while (k--)
    
51.         {
    
52.             int child;
    
53. 
    
54.             scanf("%d", &child);
    
55.             tree[id].children.push_back(child);
    
56.         }
    
57.     }
    
58.    
    
59.     pretorder(0);
    
60. 
    
61.     sort(ans.begin(), ans.end(), cmp);
    
62. 
    
63.     for (int i = 0; i < ans.size(); i++)
    
64.         for (int j = 0; j < ans[i].size(); j++)
    
65.         {
    
66.             printf("%d", ans[i][j]);
    
67.             (j < ans[i].size() - 1) ? putchar(' ') : putchar('\n');
    
68.         }
    
69.         
    
70.     return 0;
    
71. }

复制代码