题目来源Path of Equal Weight (30)注意点按照字典序从大到小输出路径题目描述Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti.The weight of a path from R to L is defined to be the sum of the weights of all the nodes along the path from R to any leaf node L.Now given any weighted tree, you are supposed to find all the paths withtheir weights equal to a given number. For example, let’s consider thetree showed in Figure 1: for each node, the upper number is the node IDwhich is a two-digit number, and the lower number is the weight of thatnode. Suppose that the given number is 24, then there exists 4different paths which have the same given weight: {10 5 2 7}, {10 4 10},{10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges inFigure 1.输入描述:Each input file contains one test case. Each case starts with a line containing 0 N 100, the number of nodes in a tree, M ( N), the number of non-leaf nodes, and 0 S 230, the given weight number. The next line contains N positive numbers where Wi (1000) corresponds to the tree node Ti. Then M lines follow, each in the format:ID K ID[1] ID[2] … ID[K]where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 00.输出描述:For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.Note: sequence {A1, A2, …, An} is said to be greater than sequence {B1, B2, …, Bm} if there exists 1 k min{n, m} such that Ai Bi for i1, … k, and Ak1 Bk1.输入例子: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输出例子:10 5 2 7 10 4 10 10 3 3 6 2 10 3 3 6 2思路简介一个很普通的 dfs先用链式前向星建树然后传一个内部的形参 res用来记录当前的路径如果遍历到叶子且符合情况就把形参 res 保存注意最后的输出是结点的权重且权重要按照字典序排序vector内部重载了,,!,,,,的运算符比较规则与字典序比较相同所以直接用 sort 即可遇到的问题无一遍过代码/** * https://www.nowcoder.com/pat/5/problem/4092 * dfs */#includebits/stdc.husingnamespacestd;constintN10010;structEdge{intto,next;Edge():to(0),next(0){}Edge(intto,intnext):to(to),next(next){}}e[N*N];inthead[N],cnt0,w[N];voidadd(intu,intv){e[cnt]{v,head[u]};head[u]cnt;}intn,m,t;voidinput(){memset(head,-1,sizeof(head));cinnmt;for(inti0;in;i){cinw[i];}for(inti0;im;i){intu;cinu;intk;cink;for(inti0;ik;i){intv;cinv;add(u,v);}}}vectorvectorintpaths;voiddfs(introot,vectorintres,intsum){res.emplace_back(w[root]);sumw[root];if(head[root]-1){if(sumt)paths.emplace_back(res);return;}for(intihead[root];i!-1;ie[i].next){dfs(e[i].to,res,sum);}}voidsolve(){input();vectorintres;dfs(0,res,0);sort(paths.begin(),paths.end(),[](vectorinta,vectorintb){returnab;});for(autopath:paths){for(autok:path){coutk ;}cout\n;}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in(in.txt,ios::in);cin.rdbuf(in.rdbuf());intT1;//cinT;while(T--){solve();}return0;}