patA1053

本文主要是介绍patA1053，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这是一道关于树遍历的题。基本的思路是使用树的静态写法，即使用数组储存树。然后使用DFS进行搜索，注意使用剪枝的思想，即遇到已经不可能产生目标的路径时就放弃这一子树。
易错点在于对结果进行排序。《算法笔记》中关于这道题的解法是有问题的，它使用的方法是在读输入时就将子节点按照权重降序排序，然后之后直接DFS即可。但这样疏忽略一个特殊情况：对于以下输入
6 4 4
1 2 2 1 2 1
0 2 1 2
1 1 3
2 1 4
3 1 5
如果对节点0的两个子节点按照权重排序，则其顺序不变，此时按照这个顺序DFS后，结果是：
1 2 1 1
1 2 2
这明显是错误的。
一种正确做法是先找到所有的结果存在vector容器中，然后使用sort()按照字典序将其降序排序即可。
代码如下：

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

using namespace std;

//节点
struct node {
	int id;
	int w;
	//子节点，按照w值降序存储
	vector<int> child;
};

const int MAX = 105;
int N, M, S;
struct node tree[MAX];
//储存路径
vector<vector<int>> path;

void input() {
	cin >> N >> M >> S;
	for (int i = 0; i < N; i++) {
		tree[i].id = i;
		int w;	cin >> w;
		tree[i].w = w;
	}

	for (int i = 0; i < M ; i++) {
		int r, n;	cin >> r >> n;
		for (int i = 0; i < n; i++) {
			int c;	cin >> c;
			tree[r].child.push_back(c);
		}
	}
}

//通过DFS求解，使用剪枝
int len = 0;	//储存当前DFS到的路径的权重
vector<int> cp;	//当前路径
void DFS(int id) {
	cp.push_back(tree[id].w);
	//更新len
	len += tree[id].w;

	//递归边界判断--已经超出目标
	if (len >= S && tree[id].child.size() > 0) {
		cp.pop_back();
		len -= tree[id].w;
		return;
	}
	//递归边界判断--找到目标路径
	if (len == S && tree[id].child.size() == 0) {
		path.push_back(cp);
	}

	for (int i = 0; i < tree[id].child.size(); i++) {
		DFS(tree[id].child[i]);
	}

	cp.pop_back();
	len -= tree[id].w;
	return;
}

int main(void) {
	input();
	DFS(0);

	//对路径排序
	sort(path.begin(), path.end(), greater<vector<int>>());

	for (int i = 0; i < path.size();i++) {
		vector<int> p=path[i];
		for (int i = 0; i < p.size(); i++) {
			cout << p[i];
			if (i == p.size() - 1)	cout << endl;
			else    cout << " ";
		}
	}

	return 0;
}

这篇关于patA1053的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！