PTA A_1053 Path of Equal Weight
传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805424153280512解：
多叉树遍历
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct node{
int weight;
vector<int> children;
} BTNode;
BTNode tree;
int total = 0, s;
vector<int> path;
vector< vector<int> > ans;
void pretorder(int root)
{
int w = tree.weight, l = tree.children.size();
path.push_back(w);
if ((total += w) == s && !l) ans.push_back(path);
for (int i = 0; i < l; i++)
pretorder(tree.children);
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.weight);
while (m--)
{
int id, k;
scanf("%d %d", &id, &k);
while (k--)
{
int child;
scanf("%d", &child);
tree.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.size(); j++)
{
printf("%d", ans);
(j < ans.size() - 1) ? putchar(' ') : putchar('\n');
}
return 0;
}
页:
[1]