正文 

当前位置： 首页 > java > java教程

1053.pathofequalweight(30)

gaoren gaoren     2022-10-01     670

关键词：

Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti. The weight of a path from R to Lis 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 Figure 1: 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 Figure 1.

技术分享图片
Figure 1

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 < 230, the given weight number. The next line contains N positive numbers where Wi (<1000) corresponds to the tree node Ti. 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 {A1, A2, ..., An} is said to be greater than sequence {B1, B2, ..., Bm} if there exists 1 <= k < min{n, m} such that Ai = Bifor i=1, ... k, and Ak+1 > Bk+1.

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


#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define max 102
vector<int>vt[max];
vector<int>result[max];
vector<int>weight;
int sweight;
int t=0;
vector<int>curpath;
void dfs(int s,int len){
	if(vt[s].empty())return;
	int tmplen = len;
	int size=vt[s].size();
	for(int i=0;i<size;i++){
		tmplen=len + weight[vt[s][i]];
		if(tmplen<sweight){
			vector<int>tmp;
			tmp=curpath;
			curpath.push_back(weight[vt[s][i]]);
			dfs(vt[s][i],tmplen);
			curpath=tmp;
		}else if(tmplen==sweight && vt[vt[s][i]].empty()){
			result[t]=curpath;
			result[t].push_back(weight[vt[s][i]]);
			t++;
		}
	}
}
bool cmp(vector<int>a,vector<int>b){
	int sizea=a.size();
	int sizeb=b.size();
	int minSize=sizea<sizeb?sizea:sizeb;
	for(int i=0;i<minSize;i++){
		if(a[i]>b[i])return true;
		else if(a[i]<b[i]) return false;
	}
	if(sizea==minSize){
		return false;
	}else {
		return true;
	}
}
int main(){
	int n,m;
	scanf("%d%d%d",&n,&m,&sweight);
	int i,j;
	int val,id,k;
	weight.resize(n);
	for(i=0;i<n;i++){
		scanf("%d",&weight[i]);
	}
	for(i=0;i<m;i++){
		scanf("%d%d",&id,&k);
		for(j=0;j<k;j++){
			scanf("%d",&val);
			vt[id].push_back(val);
		}
	}
	if(m==0){
		if(weight[0]==sweight)printf("%d
",weight[0]);
		return 0;
	}
	curpath.push_back(weight[0]);
	dfs(0,weight[0]);
	sort(result,result+t,cmp);
	for(i=0;i<t;i++){
		int size=result[i].size();
		printf("%d",result[i][0]);
		for(j=1;j<size;j++){
			printf(" %d",result[i][j]);
		}
		printf("
");
	}
	return 0;
}

　　





pat1053.pathofequalweight(30)

1053.PathofEqualWeight(30)时间限制100ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueGivenanon-emptytreewithrootR,andwithweightWi assignedtoeachtreenodeTi.The weightofapathfromRtoLisdefinedtobeth 查看详情

pat1053pathofequalweight（30分）(代码片段)

1053 PathofEqualWeight（30 分）Givenanon-emptytreewithroot R,andwithweight W?i?? assignedtoeachtreenode T?i??.The weightofapathfrom R to L isdefined 查看详情

patadvancedlevel1053pathofequalweight(代码片段)

1053PathofEqualWeight(30)（30分）Givenanon-emptytreewithrootR,andwithweightW~i~assignedtoeachtreenodeT~i~.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnod 查看详情

1053pathofequalweight(30分)难度:一般/树的遍历(代码片段)

https://pintia.cn/problem-sets/994805342720868352/problems/994805424153280512#include<bits/stdc++.h>usingnamespacestd;constintN=1e3+10;vector<int>ve[N];vector<vector< 查看详情

patadvanced1053pathofequalweight(30)[树的遍历](代码片段)

题目Givenanon-emptytreewithrootR,andwithweightWiassignedtoeachtreenodeTi.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnodeL.Nowgivenanyweightedtree,youaresupposedtofindallthepathswiththeirweightsequaltoagivennumber.Forexample,let’sconsiderthetrees... 查看详情

1053pathofequalweight(30分)(并查集)(代码片段)

Givenanon-emptytreewithroot R,andwithweight W?i?? assignedtoeachtreenode T?i??.The weightofapathfrom R to L isdefinedtobethesumoftheweightsofallthenodesalongthepathfrom R toanyleafnode L.Nowgivenanyweightedtree,youaresupposedtofindallthepat... 查看详情

pat甲题题解-1053.pathofequalweight(30)-dfs

由于最后输出的路径排序是降序输出，相当于dfs的时候应该先遍历w最大的子节点。链式前向星的遍历是从最后add的子节点开始，最后添加的应该是w最大的子节点，因此建树的时候先对child按w从小到大排序，然后再add建边。水题... 查看详情

pat1053.pathofequalweight

Givenanon-emptytreewithrootR,andwithweightWiassignedtoeachtreenodeTi.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnodeL.Nowgivenanyweightedtree,youares 查看详情

树的遍历——a1053.pathofequalweight(30)只可dfs不可bfs(代码片段)

  #include<bits/stdc++.h>#include<stdio.h>#include<stdlib.h>#include<queue>usingnamespacestd;constintMAXN=110;structNodeintweight;vector<int>child;Node[MAXN];boolcmp(inta,intb)returnNode[a].weight>Node[b].weight;intn,m,S;//结点数，边数及给定的和i... 查看详情

1053pathofequalweight（30分）（树的遍历）(代码片段)

题目大意：给出树的结构和权值，找从根结点到叶子结点的路径上的权值相加之和等于给定目标数的路径，并且从大到小输出路径#include<bits/stdc++.h>usingnamespacestd;intn,m,sum;constintN=120;structnodeintw;vector<int>p;tree[N];boolcmp(inta,in... 查看详情

pat1053pathofequalweight(代码片段)

Givenanon-emptytreewithroot R,andwithweight W?i?? assignedtoeachtreenode T?i??.The weightofapathfrom R to L isdefinedtobethesumoftheweightsofallthenodesalongthepathfrom Rtoanyleafnode L.Nowgivenanyweightedtree,youaresupposedtofindallthepathswith... 查看详情

[pat]a1053pathofequalweight(代码片段)

(要熟练！)（树的遍历）题目大意(题目链接)https://pintia.cn/problem-sets/994805342720868352/problems/994805424153280512题目大意：给出树的结构和权值，找从根结点到叶子结点的路径上的权值相加之和等于给定目标数的路径，并且从大到小输出... 查看详情

1053pathofequalweight(代码片段)

1.这道题考察的是树(注意不是二叉树，子结点个数不限，没有顺序)的先根遍历，即DFS，因为BFS做不到把祖先节点的值累计到当前结点。我这里使用了一个copyDadWeis函数实现，把父节点的权重向量拷贝给子节点&#... 查看详情

pat甲级目录

 树备注1004 CountingLeaves 1020TreeTraversals 1043IsItaBinarySearchTree 判断BST，BST的性质1053PathofEqualWeight 1064CompleteBinarySearchTree 完全二叉树的顺序存储，BST的性质1066RootofAVLTre 查看详情

10.22-10.28博客精彩回顾

...​​4.​​构建FTP文件传输服务器​​5.​​*PAT_甲级_1053PathofEqualWeight(30分)(C++)【数组排序/DFS】​​6.​​LSISAS2208阵列卡刷IT模式​​7.​​【原子样式实践】第10篇原子样式到原子设计 查看详情

1004countingleaves(30)（30分）(代码片段)

1004CountingLeaves(30)（30分）Afamilyhierarchyisusuallypresentedbyapedigreetree.Yourjobistocountthosefamilymemberswhohavenochild.InputEachinputfilecontainsonetestcase.Eachcasestartswithalinecontaining0&l 查看详情

如何写表达式 a<=20?b=30:c=30;这样 30 只使用一次？

】如何写表达式a<=20?b=30:c=30;这样30只使用一次？【英文标题】：Howtowritetheexpressiona<=20?b=30:c=30;suchthat30isusedonlyonce?【发布时间】：2021-01-3114:44:25【问题描述】：我正在关注一本关于c编程的书，遇到了这个例子：a<=20?b=30:c=30;... 查看详情

如何使用numpy数组的引用坐标处理奇怪的索引行为？(代码片段)

...。请参阅下面的示例：t=np.zeros((5,5))coord=[[2,3],[1,2]]t[coord]=30print(t)输出：[[0.0.0.0.0.][0.0.0.0.0.][0.30.0.0.0.][0.0.30.0.0.][0.0.0.0.0.]]但是如果列表只有一点：t=np.zeros((5,5))coord=[[2,3]]t[coord]=30print(t)输出：[[0.0.0.0.0.][0.0.0.0.0.][30.30.30.30.30.][30.30.30... 查看详情