题目描述：
给定一棵根节点为R的加权树（每个节点Ti具有权重Wi）。从R到L的路径的权重被定义为沿着从R到任何叶节点L的路径的所有节点的权重之和。.现在给出任何加权树，你应该找到所有的路径他们的权重等于给定的数字。
输入：
第一行：节点总数N,非叶子节点数M，给定的数字S
第二行：从0~N-1节点号的权重
后续M行：ID(节点id)，K（节点id的孩子数），ID[1] ID[2] ... ID[K]（孩子节点id）
输出：
输出路径值为给定数字S的路径（经过的每个节点的权值），并且路径需要按序输出。
note:如果存在1 <= k <min {n，m}使得Ai = Bi，则序列{A1，A2，...，An}被称为大于序列{B1，B2，...，Bm}。 i = 1，... k和Ak + 1> Bk + 1。
解题思路
采用暴力求解法。将权值存在一个邻接表chains中,从根节点00开始访问，递归遍历到每个节点的孩子节点
getSum（）{
if(该节点为叶子节点，并且路径权值==S){
路径加入结果集res中
}else{
for(遍历节点start的每一个孩子节点chain[start][i]]);){
if(现有路径权值和加上节点chain[start][i]]);的权值小于S){
将结点chain[start][i]放入路径中。
路径权值+=chain[start][i]])的权值
getSum（...,....,）
将结点chain[start][i]路径中移除。
}
}
}
}
得到结果res之后，定义排序规则，将res排序。
int cmp(vector<int> a,vector<int> b){
for(int i = 0;i<a.size()&&i<b.size();i++){
if(a[i]>b[i])return a[i]>b[i];
}
return a.size()<b.size();
}
sort(res.begin(),res.end(),cmp);
最后按输出格式输出res。
实现代码：
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> vec(100);//存储每个节点的weight
int cmp(vector<int> a,vector<int> b){
for(int i = 0;i<a.size()&&i<b.size();i++){
if(a[i]>b[i])return a[i]>b[i];
}
return a.size()<b.size();
}
void getsum(vector<vector<int> >&chain, int start,int csum,int sum,vector<vector<int> >&output, vector<int>res) {
if (csum == sum&&chain[start].size()==0) {//判断是否为叶子节点，权值是否等于Sum。
output.push_back(res);
return;
}else{
for (int i = 0; i < chain[start].size(); i++) {
if(csum + vec[chain[start][i]]<=sum){//只有加上该节点小于sum时方有可能为所求路径
res.push_back(vec[chain[start][i]]);
getsum(chain, chain[start][i], csum + vec[chain[start][i]], sum,output, res);
res.pop_back();
}
}
}
}
int main() {
int n,m,sum,k,id;//节点个数
cin >> n >> m >> sum;
for (int i = 0; i < n; i++) {
cin >> vec[i];//得到每个节点的weight
}
int t;
vector<vector<int> >chains(n);//存储树
for (int i = 0; i < m; i++) {
cin >> id >> k;
for (int j = 0; j < k; j++) {//得到每个父节点的k个子节点
cin >> t;
chains[id].push_back(t);
}
}
vector<vector<int> >output;//结果
vector<int> path;//临时路径
res.push_back(vec[0]);
getsum(chains, 0, vec[0], sum,output,path);
sort(output.begin(),output.end(),cmp); //得到正确的输出顺序
for(int i =0;i<output.size();i++){
for(int j = 0;j<output[i].size();j++){
cout<<output[i][j];
if(j<output[i].size()-1)cout<<" ";
}
cout<<endl;
}
return 0;
}
我是6J,爱吃爱玩爱笑的非典型程序~~~媛
