等重路径 Java代码 （求树中从根结点到叶子的权值，bfs，dfs）【PAT甲级1053】

输入样例：

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

输出样例：

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

求从根结点到叶子结点的总权值，可以用深搜，不断递归搜索儿子结点，当递归到叶子时，判断当前的权值总和，并将此时的路径保存，回溯时再恢复到前一步的状态。宽搜时，先将从根结点到每个结点的权值记录下来，同时记录路径，再遍历这些点的权值，找权值等于s的并且是叶子结点的权值，最后输出。

import java.io.*;
import java.util.*;

public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public static int ini() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
	
	static int n, m , s, N = 105, idx, res;
	static int []w = new int[N];
	static int []sum = new int[N];
	static int []pre = new int[N];
	static int []h = new int[N];
	static int []e = new int[N];
	static int []ne = new int[N];
	static ArrayList list = new ArrayList<>();
	static ArrayList> listall = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		n = ini(); m = ini(); s = ini();
		
		Arrays.fill(h, -1);
		Arrays.fill(pre, -1);
		for(int i = 0; i < n; i++) w[i] = ini();
		while(m-- > 0) {
			int a = ini(), k = ini();
			while(k-- > 0) add(a, ini());
		}
		
		list.add(w[0]);  // 初始时，将根节点权值保存
		res = w[0];  // 加入根结点权值
		dfs(0);
		
		Collections.sort(listall, new Comparator>() {
			@Override
			public int compare(ArrayList o1, ArrayList o2) {
				int len = Math.min(o1.size(), o2.size());
				for(int i = 0; i < len ;i++)
					if(o1.get(i) != o2.get(i)) return -(o1.get(i) - o2.get(i));
				return 0;
			}
		});
		
		for(int i = 0; i < listall.size(); i++) {
			ArrayList l = listall.get(i);
			System.out.print(l.get(0));
			for(int j = 1; j < l.size(); j++) System.out.print(" " + l.get(j));
			System.out.println();
		}
	}
	
	public static void dfs(int root) {
		if(h[root] == -1 && res == s) {  // 是叶子结点且总权值与s相等
			listall.add(new ArrayList<>(list));
		}
		
		for(int i = h[root]; i != -1; i = ne[i]) {
			int j = e[i];
			res += w[j];
			list.add(w[j]);
			dfs(j);
			res -= w[j];
			list.remove(list.size() - 1);
		}
	}
	
	public static void add(int a, int b) {
		e[idx] = b;
		ne[idx] = h[a];
		h[a] = idx++;
	}
}

import java.io.*;
import java.util.*;

public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public static int ini() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
	
	static int n, m , s, N = 105, idx;
	static int []w = new int[N];
	static int []sum = new int[N];  // 存储从根结点到当前结点的总权值
	static int []pre = new int[N];
	static int []h = new int[N];
	static int []e = new int[N];
	static int []ne = new int[N];
	static ArrayList list = new ArrayList<>();
	static ArrayList> listall = new ArrayList<>();
	
	public static void main(String[] args) throws IOException {
		n = ini();
		m = ini();
		s = ini();
		
		Arrays.fill(h, -1);
		Arrays.fill(pre, -1);
		for(int i = 0; i < n; i++) w[i] = ini();
		while(m-- > 0) {
			int a = ini(), k = ini();
			while(k-- > 0) add(a, ini());
		}
		
		bfs(0);
		
		Stack stack = new Stack<>();
		for(int i = 0; i < n; i++)
			if(sum[i] == s && h[i] == -1) {  // 是叶结点且总权值和为s
				
				for(int k = i; k != -1; k = pre[k]) stack.add(k);
				
				while(!stack.isEmpty()) list.add(w[stack.pop()]);
				
				listall.add(new ArrayList<>(list));
				list.clear();
			}
		
		Collections.sort(listall, new Comparator>() {
			@Override
			public int compare(ArrayList o1, ArrayList o2) {
				int len = Math.min(o1.size(), o2.size());
				for(int i = 0; i < len ;i++)
					if(o1.get(i) != o2.get(i)) return -(o1.get(i) - o2.get(i));
				return 0;
			}
		});
		
		for(int i = 0; i < listall.size(); i++) {
			ArrayList l = listall.get(i);
			System.out.print(l.get(0));
			for(int j = 1; j < l.size(); j++) System.out.print(" " + l.get(j));
			System.out.println();
		}
	}
	
	public static void bfs(int root) {
		Queue qu = new LinkedList<>();
		qu.add(root);
		sum[root] = w[root]; // 记录根结点的权值
		while(!qu.isEmpty()) {
			int t = qu.poll();
			for(int i = h[t]; i != -1; i = ne[i]) {
				int j = e[i];
				sum[j] = sum[t] + w[j]; // 父结点权值加当前结点权值
				qu.add(j);
				pre[j] = t;  // 记录每个结点的前驱节点
			}
		}
	}
	
	public static void add(int a, int b) {
		e[idx] = b;
		ne[idx] = h[a];
		h[a] = idx++;
	}
}