无锡高端网站建设公司哪家好自媒体平台app

NOTE：

1. 有多条路径时，有更高权值的路径要先输出。
   所以对同一层的结点，先进行从大到小的排序。
   sort(node[id].child.begin(),node[id].child.end(),cmp);

这个cmp也容易写错：vector child存的是结点号（int），比较的则是结点weight
bool cmp(int a,int b)
{
return node[a].weight>node[b].weight;
}

2. 调用DFS的初始条件：node0已经存在序列中
   DFS（0，node[0].weight） 而不是DFS（0,0）
   因为已进入dfs函数中，没有满足边界条件，就直接开始遍历node0的孩子结点，将孩子结点的weight加入原来的sum中
   所以开始dfs前，node【0】已经加入path序列。

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;int n,m,s;struct Node
{int weight;vector<int> child;
}node[maxn];bool cmp(int a,int b)
{return node[a].weight>node[b].weight;
}vector<int> path;
void DFS(int index,int sum)
{if(sum>s) return;if(sum==s){if(node[index].child.size()!=0) return;for(int j=0;j<path.size();j++){printf("%d",node[path[j]].weight);if(j!=path.size()-1) printf(" ");else printf("\n");}return;}for(int i=0;i<node[index].child.size();i++){int t=node[index].child[i];path.push_back(t);DFS(t,sum+node[t].weight);path.pop_back();}}int main()
{scanf("%d%d%d",&n,&m,&s);for(int i=0;i<n;i++){scanf("%d",&node[i].weight);}for(int i=0;i<m;i++){int id,k;scanf("%d%d",&id,&k);for(int j=0;j<k;j++){int temp;scanf("%d",&temp);node[id].child.push_back(temp);}sort(node[id].child.begin(),node[id].child.end(),cmp);}path.push_back(0);DFS(0,node[0].weight);return 0;}