目录
1，题目描述
题目大意
输入
输出
2，思路
数据结构
如何排序
如何设计DFS算法
3，心路历程
4，代码
1，题目描述
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
题目大意
给出一棵树，每个节点对应一个权值和一个编号。另外给出一个数字S，求出所有从根节点到叶子节点的权值之和为S的路径，并输出路径中各节点的权值。若路径不唯一，则按照数组从大到小有序输出。
输入
- 第一行：N节点总数 M非叶节点总数 S给定的值；
- 第二行：N个节点的权值；
- 其余M行：每个非叶节点的编号，所含子节点的个数，子节点的编号；
输出
- 按序输出所有路径中节点的值；
2，思路
设计结构体存放节点数据。利用vector存储这棵树。对树进行DFS，并将路径中节点存入temp中，并将权值之和为S的路径temp存入paths中。
对paths进行排序，按序输出；
数据结构
- struct node{int id, key；vector<int> next；} ：存放节点数据；
- vector<node> tree(100)：存放树的所有节点；
- vector<vector<int> > paths：存放所有符合条件的路径；
如何排序
//头文件
#include<algorithm>
//自定义排序函数
bool cmp1(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 false;
}
//调用
sort(paths.begin(), paths.end(), cmp1);
如何设计DFS算法
//实现过程
void DFS(int start, int weight){ //start起点编号 weight当前的累加值
weight += tree[start].key;
temp.push_back(tree[start].key); //注意区分 节点编号还是节点数据
if(tree[start].next.size() == 0){
if(weight == S){
paths.push_back(temp);
}
}
for(int i = 0; i < tree[start].next.size(); i++){
DFS(tree[start].next[i], weight);
}
temp.pop_back(); // 注意弹出!!!
}
//调用
DFS(0, 0);
3，心路历程
（感觉这一题真正恶心的地方，是对结果数组进行排序。。。）
没有对结果数组排序，别的都正确，然而只拿到了10分（看来排序是关键）
一开始想用sort对paths排序，然而没有用（并不是没有用，而是我代码的问题：将节点的编号存了起来，而不是节点的权值）。
然而使用了自定义的冒泡排序后，还有一个测试点2没通过，不过拿到了28分。然而我又陷入了沉思，排序没问题了（其实是有问题的），为什么还有测试点没过？？？（哈哈哈，上面的问题仍然存在，可能是运气爆棚，正好能通过例子）。
上网查询后，都说测试点2是只有一个根节点的数据 ，然而我的代码对只有一个根节点，也可以正常运行。。。（绝了，我甚至想动用重启大法，，，但细想作为科班出身的我，绝不应该怀疑编译器，便又继续探索。。。）
没办法，只好求助牛客爸爸，终于找到了错误的举例。（不知道如何用牛客网测试数据的同学，可以戳这里【PAT数据测试——牛客网】）
测试用例:
10 2 3
1 1 1 2 2 2 2 2 2 2
00 8 01 03 04 05 06 07 08 09
01 1 02
对应输出应该为:
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 1 1
你的输出为:
1 2
1 1 1
1 2
1 2
1 2
1 2
1 2
1 2
哎呦我去，怎么还是排序的问题。。。
没办法，只好从头捋一遍了。终于发现了奇怪的地方！
（配色有点奇葩，不喜勿喷，嘤嘤嘤）
真相大白了，就是把节点编号当成节点数据进行了运算。
4，代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
int id, key;
vector<int> next;
};
int N, M, S; //N树的结点 M非叶节点的节点数目 S给定的权值
vector<vector<int> > paths;
vector<int> temp;
vector<node> tree(100);
void DFS(int start, int weight){ //start起点编号 weight当前的累加值
weight += tree[start].key;
temp.push_back(tree[start].key); //注意区分 节点编号还是节点数据
if(tree[start].next.size() == 0){
if(weight == S){
paths.push_back(temp);
}
}
for(int i = 0; i < tree[start].next.size(); i++){
DFS(tree[start].next[i], weight);
}
temp.pop_back(); // 注意弹出!!!
}
bool cmp1(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 false;
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif
scanf("%d%d%d", &N, &M, &S);
int k;
for(int i = 0; i < N; i++){
scanf("%d", &k);
tree[i].key = k;
}
for(int i = 0; i < M; i++){
int id, num, temp;
scanf("%d %d", &id, &num);
for(int j = 0; j < num; j++){
scanf("%d", &temp);
tree[id].next.push_back(temp);
}
}
DFS(0, 0);
sort(paths.begin(), paths.end(), cmp1);
for(int i = 0; i < paths.size(); i++){
printf("%d", paths[i][0]);
for(int j = 1; j < paths[i].size(); j++){
printf(" %d", paths[i][j]);
}
printf("\n");
}
return 0;
}
