[PAT解题报告] Path of Equal Weight
给定一棵树，每个节点有一个值，找到从根到叶子，所有和为给定值的路径。
其实题目不难。因为路径规定比较死，从根到叶子，所以路径树最多等于叶子树。我们遍历整个树，例如dfs，到达叶子时，我们有了这条路径本身，以及这条路径的权值和，如果和满足要求，我们就保留它，最后输出注意按字典序排序……
所以本质就是一个dfs。
代码：
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[102],w;
vector<int> con[102];
bool mark[102];
void dfs(int now,int sum, vector<int> &path, vector<vector<int> > &answer) {
path.push_back(a[now]);
sum += a[now];
if (con[now].empty()) {
if (sum == w) {
answer.push_back(path);
}
}
else {
for (int i = 0; i < con[now].size(); ++i) {
dfs(con[now][i], sum, path, answer);
}
}
path.pop_back();
}
int main() {
int n, m;
scanf("%d%d%d",&n,&m,&w);
for (int i = 0; i < n; ++i) {
scanf("%d",a + i);
}
for (;m;--m) {
int x,y;
for (scanf("%d%d",&x,&y);y;--y) {
int z;
scanf("%d",&z);
con[x].push_back(z);
mark[z] = true;
}
}
for (m = 0; mark[m]; ++m)
;
vector<int> path;
vector<vector<int> > answer;
dfs(m, 0, path, answer);
sort(answer.begin(),answer.end());
for (int i = answer.size() - 1; i >= 0; --i) {
for (int j = 0; j < answer[i].size(); ++j) {
if (j) {
putchar(' ');
}
printf("%d",answer[i][j]);
}
puts("");
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1053
安克HR面27人在聊