PAT(Advanced) 1053 Path of Equal Weight（30 分）

Given a non-empty tree with root R, and with weight W​i​​ assigned to each tree node T​i​​. 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 with their weights equal to a given number. For example, let's consider the tree showed in the following figure: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different 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 in the figure.

Input Specification:

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<2​30​​, the given weight number. The next line contains N positive numbers where W​i​​ (<1000) corresponds to the tree node T​i​​. 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.

Output Specification:

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 {A​1​​,A​2​​,⋯,A​n​​} is said to be greater than sequence {B​1​​,B​2​​,⋯,B​m​​} if there exists 1≤k<min{n,m} such that A​i​​=B​i​​ for i=1,⋯,k, and A​k+1​​>B​k+1​​.

解答：

该题可以直接用dfs求解，在找到符合条件的叶节点时，便将它保存下来。

那么如何求其路径呢，那么我们可以用一个数组来保存一个节点的父节点， 即tree[i] = j; 那么节点 i 的父节点就是 j 。然后通过递归来求路径，思路比较清晰；

那么如何对路径进行排序呢？这时我们可以在保存路径时，对一个根的子树按权值排序，这样，我们用dfs遍历时，便会先访问权值高的节点，这样就不需要另外排序啦。

---------------------------------------------------------------------------------------------

今天，我在博客 1053. Path of Equal Weight (30)-PAT甲级真题(树的遍历)中找到了一个输出路径的更简洁的方法，时间效率其实大致相同。就是每次遍历时，都保存下当前的节点，并记录当前是第几个节点，这样便可以愉快地输出路径了。代码见下。

学无止境，加油！

AC代码如下：

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

#define maxn 105

using namespace std;

int n, m, s;
vector<int> weights;
int tree[maxn];  //保存第i个节点的父亲 
vector<int> e[maxn];
vector<int> paths;  //记录符合条件的叶节点 

void dfs(int v, int w)
{
	if(e[v].size() == 0 && w == s){
		paths.push_back(v);
	}	
	for(int i = 0; i < e[v].size(); ++i)
	{
		int node = e[v][i];
		dfs(node, w + weights[node]);
	}
}

void print(int v)
{
	if(v == 0)
	{
		printf("%d", weights[v]);
		return;	
	}	
	print(tree[v]);
	printf(" %d", weights[v]);
}

bool cmp(int v1, int v2)
{
	return weights[v1] > weights[v2];
}

int main()
{
	scanf("%d %d %d", &n, &m, &s);
	
	for(int i = 0; i < n; ++i)
	{
		int weight;
		scanf("%d", &weight);
		weights.push_back(weight);
	}
	for(int i = 0; i < m; ++i)
	{
		int v, nc;
		
		scanf("%d %d", &v, &nc);
		for(int j = 1; j <= nc; ++j)
		{
			int child;
			scanf("%d", &child);
			e[v].push_back(child);
			tree[child] = v;
		}
		//对边按权值从大到小排序，这样可以保证输出有序 
		sort(e[v].begin(), e[v].end(), cmp);
	}

	dfs(00, weights[0]);
	
	for(int i = 0; i < paths.size(); ++i)
	{
		print(paths[i]);
		printf("\n");
	}
	return 0;
}

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

#define maxn 105

using namespace std;

int n, m, s;
vector<int> weights;
int tree[maxn];  //保存第i个节点的父亲 
vector<int> e[maxn];
vector<int> path(maxn);  //记录符合条件的叶节点 

void dfs(int v, int num, int w)
{
	if(e[v].size() == 0 && w == s){
		for(int i = 0; i < num; ++i)
		{
			printf("%d%c", weights[path[i]], i != num-1 ? ' ' : '\n');
		}
		return;
	}	

	for(int i = 0; i < e[v].size(); ++i)
	{
		int node = e[v][i];
		path[num] = node; 
		dfs(node, num+1, w + weights[node]);
	}
}

bool cmp(int v1, int v2)
{
	return weights[v1] > weights[v2];
}

int main()
{
	scanf("%d %d %d", &n, &m, &s);
	
	for(int i = 0; i < n; ++i)
	{
		int weight;
		scanf("%d", &weight);
		weights.push_back(weight);
	}
	for(int i = 0; i < m; ++i)
	{
		int v, nc;
		
		scanf("%d %d", &v, &nc);
		for(int j = 1; j <= nc; ++j)
		{
			int child;
			scanf("%d", &child);
			e[v].push_back(child);
			tree[child] = v;
		}
		//对边按权值从大到小排序，这样可以保证输出有序 
		sort(e[v].begin(), e[v].end(), cmp);
	}
	
	path[0] = 0;
	dfs(00, 1, weights[0]);

	return 0;
}