• 1053 Path of Equal Weight

    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 the following figure: 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 the figure.

     

    Input Specification:

    Each input file contains one test case. Each case starts with a line containing 0 

    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≤kBk+1​.

    Sample Input:

    1. 20 9 24
    2. 10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
    3. 00 4 01 02 03 04
    4. 02 1 05
    5. 04 2 06 07
    6. 03 3 11 12 13
    7. 06 1 09
    8. 07 2 08 10
    9. 16 1 15
    10. 13 3 14 16 17
    11. 17 2 18 19

    Sample Output:

    1. 10 5 2 7
    2. 10 4 10
    3. 10 3 3 6 2
    4. 10 3 3 6 2

    题目大意

    给你树的路径和权值，请找出找从根结点到叶⼦结点路径上的权值相加之和等于Key的
    路径，并且从⼤到⼩输出路径

    思路

    DFS暴力遍历即可

    C/C++ 

    1. #include
    2. using namespace std;
    3. void DFS(int now,int sum);
    4. vectorint>> result;
    5. vector<int> child[10001],op;
    6. int power[10001],N,M,key,a,b,c;
    7. bool cmp(vector<int>& x,vector<int>& y){
    8.     for(int z=0;z<min(x.size(),y.size());z++){
    9.         if(power[x[z]]!=power[y[z]]) return power[x[z]] > power[y[z]];
    10.     }
    11.     return false;
    12. }
    13. int main()
    14. {
    15.     cin >> N >> M >> key;
    16.     for(int z=0;z> power[z];
    17.     while (M--){
    18.        cin >> a >> b;
    19.         while (b--){
    20.             cin >> c;
    21.             child[a].push_back(c);
    22.         }
    23.     }
    24.     DFS(0,power[0]);
    25.     if(result.size()>1) sort(result.begin(),result.end(),cmp);
    26.     for(const auto& x:result){
    27.         cout << power[0];
    28.         for(int y:x) cout << " " << power[y];
    29.         putchar('\n');
    30.     }
    31.     return 0;
    32. }
    33. void DFS(int now,int sum)
    34. {
    35.     if(child[now].empty()){
    36.         if(sum==key) result.push_back(op);
    37.         return;
    38.     }else{
    39.         for(int x:child[now]) {
    40.             op.push_back(x);
    41.             DFS(x,sum+power[x]);
    42.             op.pop_back();
    43.         }
    44.     }
    45. }

     

  • 相关阅读:
    力扣(LeetCode)16. 最接近的三数之和(C++)
    电脑监控软件：保护企业核心信息资产，防止数据泄露
    AI大模型探索之路-训练篇3：大语言模型全景解读
    Java容器（arraylist+vector源码+stack）
    自己动手写一个分库分表中间件（九）兼容性处理之事务之 Spring 怎么看是一个事务
    云计算学习笔记——第四章 存储虚拟化
    IPv4用的好好的，为什么我们要换IPv6？
    【Node.js从基础到高级运用】六、创建第一个 Node.js 应用
    Docker 必知必会1----初识
    【Java】中Maven依赖详解
  • 原文地址：https://blog.csdn.net/daybreak_alonely/article/details/127875157