• 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. }

     

  • 相关阅读:
    HumanNeRF：从2D视频提取动态人像，并转换为3D模型
    mybatis源码探索之代理封装阶段
    计算机毕业设计Java新冠疫苗预约系统(源码+系统+mysql数据库+Lw文档）
    微软Edge浏览器的辅助功能设置：提升用户体验的指南
    【Linux】 ls命令使用
    [linux] 网络基础
    DELETE、TRUNCATE 和 DROP 在MySQL中的区别及使用示例
    【服务器数据恢复】linux ext3下mysql数据库数据恢复案例
    【JAVA】获取当前项目的classpath路径
    【Python】新手入门学习：详细介绍里氏替换原则（LSP）及其作用、代码示例
  • 原文地址：https://blog.csdn.net/daybreak_alonely/article/details/127875157