1053 Path of Equal Weight

题目大意：

给一棵结点数为n，非叶结点数为m的树，然后给一个权值s。接下来给出n个结点的权值（顺序就是结点ID编号），依次给出m个父节点的子节点编号，要求按照从大到小的顺序（按字典序理解）输出路径权值和为s的路径结点。

解题思路：

这个题用DFS或者记忆化DP都可以写，这里给出DFS的方法，用一个vectot保存路径，关于输出字典序有个小技巧，就是在给父节点输入子节点的时候，可以按照权值大小排序子节点，这样在DFS的时候就优先搜索出字典序大的路径。
代码如下：

#include<iostream>
#include<cstdio>
#include<fstream>
#include<set>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<iomanip>
#include<cstdlib>
#include<list>
#include<queue>
#include<stack>
#include<algorithm>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define meminf(a) memset(a,inf,sizeof(a))
//vector ::iterator it;
//set<int>::iterator iter;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int n,m,s;
vector<int> path;
struct node
{
  int weight;//权值
  vector<int> child;//存放子节点
}nod[110];
int cmp(int a,int b)//子节点权值按照从大到小排序
{
  return nod[a].weight>nod[b].weight;
}
void dfs(int id,int sum)
{
//  cout<<id<<' '<<sum<<endl;
  if(sum==s)
  {
    if(nod[id].child.size()) return ;//如果是父节点，返回
    else
    {
      cout<<path[0];
      for(int i=1;i<path.size();i++)cout<<' '<<path[i];//输出路径
      cout<<endl;
    }
  }
  else if(sum<s)//当前路径和未达到s，继续搜索
  {
    for(int i=0;i<nod[id].child.size();i++)
    {
      int tmp=nod[id].child[i];
      path.push_back(nod[tmp].weight);//加入路径
      dfs(tmp,sum+nod[tmp].weight);
      path.pop_back();
    }
  }
  else return;
}
int main()
{
  scanf("%d %d %d",&n,&m,&s);
  for(int i=0;i<n;i++)scanf("%d",&nod[i].weight);
  for(int i=0;i<m;i++)
  {
    int id,num;
    scanf("%d %d",&id,&num);
    for(int i=0;i<num;i++)
    {
      int tmp;
      scanf("%d",&tmp);
      nod[id].child.push_back(tmp);
    }
    int len=nod[id].child.size();
    sort(nod[id].child.begin(),nod[id].child.end(),cmp);//子节点按照权值从大到小排序
  }
  path.push_back(nod[0].weight);
  dfs(0,nod[0].weight);

//  std::ios::sync_with_stdio(false);
//  cin.tie(0);
//  freopen("test.txt","r",stdin);
//  freopen("output.txt","w",stdout);
 return 0;
}