目录
1，题目描述
题目大意
输入
输出
2，思路
数据结构
如何排序
如何设计DFS算法
3，心路历程
4，代码
1，题目描述
Sample Input:
20 9 2410 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 200 4 01 02 03 0402 1 0504 2 06 0703 3 11 12 1306 1 0907 2 08 1016 1 1513 3 14 16 1717 2 18 19
Sample Output:
10 5 2 710 4 1010 3 3 6 210 3 3 6 2题目大意
给出一棵树，每个节点对应一个权值和一个编号。另外给出一个数字S，求出所有从根节点到叶子节点的权值之和为S的路径，并输出路径中各节点的权值。若路径不唯一，则按照数组从大到小有序输出。
输入
输出
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 31 1 1 2 2 2 2 2 2 200 8 01 03 04 05 06 07 08 0901 1 02对应输出应该为:1 21 21 21 21 21 21 21 1 1你的输出为:1 21 1 11 21 21 21 21 21 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;}