1053 Path of Equal Weight (30分)

题目

Given a non-empty tree with root $R$R, and with weight $W_i$Wi​ assigned to each tree node $T_i$Ti​. The weight of a path from $R$R to $L$L is defined to be the sum of the weights of all the nodes along the path from $R$R to any leaf node $L$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\lt N\le100$0<N≤100, the number of nodes in a tree, $M(\lt N)$M(<N), the number of non-leaf nodes, and $0\lt S\lt2^{30}$0<S<230, the given weight number. The next line contains $N$N positive numbers where $W_i(\lt1000)$Wi​(<1000) corresponds to the tree node $T_i$Ti​. Then $M$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 $\{A_1,A_2,\cdots,A_n\}${A1​,A2​,⋯,An​} is said to be greater than sequence $\{B_1,B_2,\cdots,B_m\}${B1​,B2​,⋯,Bm​} if there exists $1\le k\lt min\{n,m\}$1≤k<min{n,m} such that $A_i=B_i$Ai​=Bi​ for $i=1,\cdots,k,$i=1,⋯,k, and $A_{k+1}\gt B_{k+1}$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

题目大意

给出一棵树，树的每个节点按$0\rightarrow N$0→N编号，并且每个节点给定权值，给出一个权值和，要求输出这棵树上所有从根节点到叶节点权值之和等于这个给定值。

技巧

1. 树的遍历采用递归；
2. 这个题并不需要建树，本身题目给出的节点信息刚好与邻接表对应，可直接作为邻接表使用，同时这也给我们一个经验，存储树就可以采用这种形式；
3. 当前节点的孩子节点可以用vector存储；
4. 遍历时设立两个变量，vector用于存储路径，w_sum记录权值和，每层递归结束后记得回代即可；

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> node[100], w(100);
vector<vector<int> > ans;
vector<int> temp;
int wsum = 0;
int n, m, s;

void travel(int r){
    temp.push_back(w[r]);
    wsum += w[r];
    for(int i=0; i<node[r].size(); i++)
        travel(node[r][i]);
    if(node[r].size() == 0 && wsum == s){
        ans.push_back(temp);
    }
    temp.pop_back();
    wsum -= w[r];
}

bool cmp(vector<int> a, vector<int> b){
    int t = min(a.size(), b.size());
    for(int i=0; i<t; i++)
        if(a[i] != b[i])
            return a[i] > b[i];
    return false;
}

int main(){
    scanf("%d%d%d", &n, &m, &s);
    for(int i=0; i<n; i++)
        scanf("%d", &w[i]);
    for(int i=0; i<m; i++){
        int r, t, c;
        scanf("%d%d", &r, &t);
        while(t--){
            scanf("%d", &c);
            node[r].push_back(c);
        }
    }
    travel(0);
    sort(ans.begin(), ans.end(), cmp);
    for(int i=0; i<ans.size(); i++){
        for(int j=0; j<ans[i].size(); j++){
            if(j)
                printf(" ");
            printf("%d", ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}