1053 Path of Equal Weight

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

给出该树，要求输出符合条件的路径。

　　这个题目在键树时可以用静态数组来写，运用dfs函数来写，比较简单。

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int Max = 110;
struct Node {
    int wegiht;
    vector<int>child;
}node[Max];//静态树
bool cmp(int a, int b) {
    return node[a].wegiht>node[b].wegiht;
}//按节点的权重，从大到小排列
int n, m, s, path[Max];
void dfs(int index, int numnode, int sum) {
    if (sum > s)return;
    if (sum == s) {
        if (!node[index].child.empty())return;
        for (int i = 0; i < numnode; i++) {//如果该结点为叶节点，则输出路径
            if (i != 0)cout << " ";
            cout << node[path[i]].wegiht;
            if (i == numnode - 1)cout << endl;
        }
    }
    for (int i = 0; i < node[index].child.size(); i++) {
        int child = node[index].child[i];
        path[numnode] = child;//path这个数组是从0开始的
        dfs(child, numnode + 1, sum + node[child].wegiht);//进入递归
    }
}
int main() {
    cin >> n >> m >> s;//n个结点和m个非叶结点。
    for (int i = 0; i < n; i++) {
        cin>> node[i].wegiht;
    }
    int id, k;
    for (int i = 0; i < m; i++) {
        cin >> id >> k;
        for (int j = 0; j < k; j++) {
            int temp;
            cin >> temp;
            node[id].child.push_back(temp);
        }
        sort(node[id].child.begin(), node[id].child.end(), cmp);//按节点权重由大到小排序。
    }
    path[0] = 0;
    dfs(0, 1, node[0].wegiht);
    return 0;
}