PAT A1053 Path of Equal Weight

Sample Input:

20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19

Sample Output:

10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2

word	meaning
assign	v.指定、分配

• 思路1：
  DFS，用一个数组Res记录当前路径上的node，如果到达叶子节点时刚好权重和==s，打印出Res中node的Weight

• TIPS:
  要求non-increasing输出，DFS应每次从孩子最右向左进行（输入时要将每个节点的child从小到大排好序）

• code1:

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 110;

struct Node{
	int data, weight;
	vector<int> child;
}node[maxn];

bool cmp(int a, int b){
	//Q: a.b要使用int，不能直接用Node a, Node b 
	return node[a].weight < node[b].weight;
}
int n, m, s;	//n节点数，m非叶节点数，s给出的权值 
int Res[maxn];
void DFS(int root, int sizeRes, int sum){
	if(sum > s) return;
	//当前权值超过s，直接返回 
	if(sum == s){
	//当前权值==s,判断是否刚好走到一个叶节点 
		if(node[root].child.size() != 0) return;
		//未到叶子，直接返回 
		for(int i = 0; i < sizeRes; ++i){
		//刚好到达叶节点，输出路径Res[]
			printf("%d", node[Res[i]].weight);
			if(i < sizeRes-1) printf(" "); 
			else printf("\n");
		}
	}
	int numChild = node[root].child.size();
	for(int i = numChild-1; i >= 0; --i){
		//要求non-increasing,故要从右（weight大）向左 
		Res[sizeRes] = node[root].child[i];
//		DFS(node[root].child[i], sizeRes+1, sum+node[root].weight);	//权值加的是下一次迭代的（孩子的） 
		DFS(node[root].child[i], sizeRes+1, sum+node[node[root].child[i]].weight);
	} 
	return;
}

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 f, num;
		scanf("%d %d", &f, &num);
		for(int j = 0; j < num; ++j){
			int ch;
			scanf("%d", &ch);
			node[f].child.push_back(ch);
		}
		sort(node[f].child.begin() , node[f].child.end(), cmp);
	}
	DFS(0, 1, node[0].weight);
	return 0;
}

• 如果改为用vector存储Res:每次递归时将递归元素（root）push进vector，回溯时（递归完这个元素时：从递归函数出来），将这个元素pop出去

• code 1-2：

vector<int> Res; 
void DFS(int root, int sum){
	Res.push_back(root);
	if(sum > s) return;
	if(sum == s){
		if(node[root].child.size() != 0) return;
		for(int i = 0; i < Res.size(); ++i){
			printf("%d", node[Res[i]].weight);
			if(i < Res.size()-1) printf(" "); 
			else printf("\n");
		}
	}
	int numChild = node[root].child.size();
	for(int i = numChild-1; i >= 0; --i){
		DFS(node[root].child[i], sum+node[node[root].child[i]].weight);
		Res.pop_back();
	} 
	return;
}