PAT甲级 1053 Path of Equal Weight
PAT甲级 1053 Path of Equal Weight
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 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.
来吧，让我详细翻译一下题意吧。
给一个r个结点的非空树，并且每个节点ti的权重为wi，从R节点到L节点的路途权重=途中各个节点的权重和。
现在给出一个加权树,你应该找到所有的路径权重=一个给定的数字。让我们考虑以下图中的树。
每个节点的ID是一个两位数,每个圆圈中横线下面的数字是该节点的权重。假设给定的数字是24。
那么存在4不同的路径也有相同的给定的重量:{ 10 5 2 7 },{ 10 4 },{ 10 3 3 6 2 }和{ 10 3 3 6 2 },这对应于图中的红色边。
input:
第一行为 N结点个数 M非叶节点数，也就算是子树的树根 S树的子路径的权值和
下一行给出每个结点的权重，顺序是从结点1-N
再下M行是
：每个子树树根的结点 直接相连的子节点的个数 每个直接相连的点
如：
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
再次提示：由于这是考研题，所以每个变量的数据量不算特别大，才10^6的样子，放心大胆地拿vector建图就行，不用什么前向星连式存储省内存，放心大胆地vector和dfs的莽吧！
题目大意：给出树的结构和权值，找从根结点到叶子结点的路径上的权值相加之和等于给定目标数的路径，并且从大到小输出路径
思路：
这道题还是很oK的，用邻接表方式储存子节点，并对每个父节点所有的子节点按权重排序。
再用dfs，在dfs中保存路径，当dfs到叶节点时，即该节点的邻接表为空时，判断该条路径的和是否与题目要求的相等，相等则输出路径。
注意在每次对一个节点的所有邻接表中的节点访问后，就要pop出，sum也要减去相应节点的weight，以维持路径和sum的正确性。
代码：利用vector存储的dfs的写法！
#include
#include
#include
using namespace std;
int weight[101],n,m,s,father,son,num;
vector<int>list[101],res;
int sum=0;
int cmp(int n,int m)//按权值升序排序
{ return weight[n]>weight[m];}
void dfs(int root,int n)
{
res.push_back(weight[root]);
sum+=weight[root];//每到一个节点就加上当前状态的权值
if(list[root].size()==0)//到栈底的出栈操作
{
if(sum==s)
{
for(int i=0;i<res.size();i++)
i>0?(cout<<" "<<res[i]):(cout<<res[i]);
cout<<endl;
}
sum-=res[res.size()-1];
res.pop_back();
return;
}
for(int i=0;i<list[root].size();i++)
dfs(list[root][i],sum);
sum-=res[res.size()-1];//晦朔
res.pop_back();//出栈，跳出当前节点
}
int main()
{
cin>>n>>m>>s;
for(int i=0;i<n;i++)
cin>>weight[i];//每条边的权值
for(int i=0;i<m;i++)
{
cin>>father>>num;
for(int j=0;j<num;j++)
{
cin>>son;
list[father].push_back(son);//利用vector存边这是我比较爱用的手法
} //其实打比赛时数据结构的代码手比较核心的问题就是“建立模型和存储结构”
sort(list[father].begin(),list[father].end(),cmp);//对同父节点的每条边进行排序
} //以保障dfs时的输出顺序
dfs(0,0);
return 0;
}
</num;j++)
</m;i++)
</n;i++)
</res[i]);
</res[i]):(</res.size();i++)思路一样！只不过是利用了stack和向前存储的写法！很好但我玩的不是很熟，但二者在时间空间复杂度上都差不多！
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 101;
int weigh[MAX];
map<int,vector<int> >adjlist;
int pre[MAX];
stack<int> path;
void print(int p){
while(p!=-1){
path.push(p);
p = pre[p];
}
printf("%d",weigh[path.top()]);
path.pop();
while(!path.empty()){
printf(" %d",weigh[path.top()]);
path.pop();
}
printf("\n");
}
void dfs(int p,const int s,int sum){
sum += weigh[p];
if(sum>s)return;
if(sum==s && adjlist[p].empty()){//权值和等于s且为叶子，打印路径
print(p);
return;
}
//说明到此处的权值和小于s，若p为叶子，则返回，此路无解
if(adjlist[p].empty())return;
//遍历其各个孩子路径
vector<int>::reverse_iterator ite = adjlist[p].rbegin();
for(;ite!=adjlist[p].rend();++ite){
dfs(*ite,s,sum);
}
}
void init(int n){
int i;
for(i=0;i<n;++i){
pre[i] = -1;
}
}
bool cmp(int a,int b){
return weigh[a]<weigh[b];
}
int main(){
//freopen("in.txt","r",stdin);
int n,m,s,i,k,id,sid,ln;
scanf("%d %d %d",&n,&m,&s);
for(i=0;i<n;++i){
scanf("%d",&weigh[i]);
}
init(n);
while(m--){
scanf("%d %d",&id,&ln);
while(ln--){
scanf("%d",&sid);
adjlist[id].push_back(sid);
pre[sid] = id;//记录节点的前驱，打印路径时使用
}
sort(adjlist[id].begin(),adjlist[id].end(),cmp);
}
dfs(0,s,0);
return 0;
}
</n;++i){
</weigh[b];
</n;++i){