PTA A_1053 Path of Equal Weight

798236606

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

解：
多叉树遍历

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

typedef struct node{
    int weight;
    vector<int> children;
} BTNode;

BTNode tree[105];
int total = 0, s;
vector<int> path;
vector< vector<int> > ans;

void pretorder(int root)
{
    int w = tree[root].weight, l = tree[root].children.size();

    path.push_back(w);
    if ((total += w) == s && !l) ans.push_back(path);

    for (int i = 0; i < l; i++)
        pretorder(tree[root].children[i]);

    path.pop_back();
    total -= w;
}

bool cmp(vector<int> a, vector<int> b)
{
    return a > b;
}

int main(void)
{
    int n, m;
    scanf("%d %d %d", &n, &m, &s);
    if (!n) return 0;

    for (int i = 0; i < n; i++)
        scanf("%d", &tree[i].weight);

    while (m--)
    {
        int id, k;

        scanf("%d %d", &id, &k);  
        while (k--)
        {
            int child;

            scanf("%d", &child);
            tree[id].children.push_back(child);
        }
    }
    
    pretorder(0);

    sort(ans.begin(), ans.end(), cmp);

    for (int i = 0; i < ans.size(); i++)
        for (int j = 0; j < ans[i].size(); j++)
        {
            printf("%d", ans[i][j]);
            (j < ans[i].size() - 1) ? putchar(' ') : putchar('\n');
        }
        
    return 0;
}