1053. Path of Equal Weight (30)

1. 原题： https://www.patest.cn/contests/pat-a-PRactise/1053

2. 思路：

3. 源码（已AC）：

#include<iostream>#include<algorithm>//使用sort函数#include<vector>using namespace std;vector<int> pwt;//存储路径的每个结点权值vector<int> nwt;//存储树的每个结点权值int N, M, S;//分别为总结点数， 非叶子节点数，给出的权值struct Node{	bool Operator<(const Node &b) const//重载比较运算符	{		return wgt > b.wgt;	}	int id;//结点编号	int wgt;//权值};vector< vector<Node> > vtree;//类似图的邻接表表示，嵌套vector，表示结点的孩子void dfs(int s, int sum);//dfs，参数为遍历起点，累计的权值int main(void){	//freopen("in.txt", "r", stdin);	cin >> N >> M >> S;	nwt.resize(N);//重新定义数组大小	vtree.resize(N);	for (int i = 0; i < N; i++)//保存每个结点权值		cin >> nwt[i];	for (int i = 0; i < M; i++ )	{		int par, num;		cin >> par >> num;		vtree[par].resize(num);		for (int j = 0; j < num; j++)//每个孩子结点压入父结点的数组中		{			Node tem;			cin >> tem.id;			tem.wgt = nwt[tem.id];			vtree[par][j] = tem;		}		sort(vtree[par].begin(), vtree[par].end());//降序排序	}		dfs(0, 0);	return 0;}void dfs(int s, int sum){	sum += nwt[s];	pwt.push_back(nwt[s]);	if (sum > S)//大于直接返回上一级		return;	if (sum == S && vtree[s].empty())//相等且为叶子结点，为所求，输出结果	{		for (int i = 0; i < pwt.size(); i++)		{			if (i == 0)				cout << pwt[i];			else				cout << ' ' << pwt[i];		}		cout << endl;		return;	}	if (sum < S && vtree[s].size() > 0)//小于的话，继续dfs	{		for (int i = 0; i < vtree[s].size(); i++)		{			dfs(vtree[s][i].id, sum);			pwt.pop_back();//从dfs里返回后要弹出最后压入的		}	}	return;}