PAT甲级-1053 Path of Equal Weight (30分)

题目：1053 Path of Equal Weight (30分)

分析：排序题，这里输出的时候直接sort，没有写cmp函数，则从尾部开始输出，或者也可以在输入的时候对每个节点的孩子进行sort（很多博客都是这样写的，代码都一样，但还是要根据自己的思路来比较好）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#define MAX 999999999
using namespace std;
int n,m,k;
struct node{
    int id,weight;
    vector<int>child;
};
node node[101];
int visi[101];
int dis;
vector<int>temp;
vector<vector<int>>ans;
void dfs(int root)
{
    visi[root] = 1;
    if(node[root].child.size() == 0 && dis == k)
        ans.push_back(temp);
    for(int i = 0;i<node[root].child.size();i++)
    {
        if(!visi[node[root].child[i]])
        {
            dis += node[node[root].child[i]].weight;
            temp.push_back(node[node[root].child[i]].weight);
            dfs(node[root].child[i]);
            dis -= node[node[root].child[i]].weight;
            temp.pop_back();
        }
    }
    visi[root] = 0;
}
int main()
{
    cin>>n>>m>>k;
    for(int i = 0;i<n;i++)
    {
          node[i].id = i;
          cin>>node[i].weight;
    }
    for(int i = 0;i<m;i++)
    {
        int id,num;
        cin>>id>>num;
        for(int j = 0;j<num;j++)
        {
            int x;
            cin>>x;
            node[id].child.push_back(x);
        }
    }
    dis = node[0].weight;
    temp.push_back(node[0].weight);
    dfs(0);
    sort(ans.begin(),ans.end(),cmp);
    for(int i = ans.size() - 1;i >= 0;i--)
    {
        for(int j = 0;j<ans[i].size();j++)
            if(j != ans[i].size() - 1)
                cout<<ans[i][j]<<" ";
            else
                cout<<ans[i][j]<<endl;
    }
    return 0;
}