PAT_1042 Path of Equal Weight

题目描述：

给定一棵根节点为R的加权树（每个节点Ti具有权重Wi）。从R到L的路径的权重被定义为沿着从R到任何叶节点L的路径的所有节点的权重之和。.现在给出任何加权树，你应该找到所有的路径他们的权重等于给定的数字。

输入：

第一行：节点总数N,非叶子节点数M，给定的数字S
第二行：从0~N-1节点号的权重
后续M行：ID(节点id)，K（节点id的孩子数），ID[1] ID[2] ... ID[K]（孩子节点id）

输出：

输出路径值为给定数字S的路径（经过的每个节点的权值），并且路径需要按序输出。
note:如果存在1 <= k <min {n，m}使得Ai = Bi，则序列{A1，A2，...，An}被称为大于序列{B1，B2，...，Bm}。 i = 1，... k和Ak + 1> Bk + 1。

解题思路

采用暴力求解法。将权值存在一个邻接表chains中,从根节点00开始访问，递归遍历到每个节点的孩子节点

getSum（）{
   if(该节点为叶子节点，并且路径权值==S){
        路径加入结果集res中
    }else{
      for(遍历节点start的每一个孩子节点chain[start][i]]);){
          if(现有路径权值和加上节点chain[start][i]]);的权值小于S){
                将结点chain[start][i]放入路径中。
                路径权值+=chain[start][i]])的权值
                getSum（...,....,）
                将结点chain[start][i]路径中移除。
        }
      }
  }
}

得到结果res之后，定义排序规则，将res排序。

int cmp(vector<int> a,vector<int> b){
   for(int i = 0;i<a.size()&&i<b.size();i++){
       if(a[i]>b[i])return a[i]>b[i];
   }
   return a.size()<b.size();
}
sort(res.begin(),res.end(),cmp);

最后按输出格式输出res。

实现代码：

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> vec(100);//存储每个节点的weight
int cmp(vector<int> a,vector<int> b){
   for(int i = 0;i<a.size()&&i<b.size();i++){
       if(a[i]>b[i])return a[i]>b[i];
   }
   return a.size()<b.size();
}
void getsum(vector<vector<int> >&chain, int start,int csum,int sum,vector<vector<int> >&output, vector<int>res) {
   if (csum == sum&&chain[start].size()==0) {//判断是否为叶子节点，权值是否等于Sum。
       output.push_back(res);
       return;
   }else{
       for (int i = 0; i < chain[start].size(); i++) {
           if(csum + vec[chain[start][i]]<=sum){//只有加上该节点小于sum时方有可能为所求路径
                res.push_back(vec[chain[start][i]]);
                getsum(chain, chain[start][i], csum + vec[chain[start][i]], sum,output, res);
                res.pop_back();
           }
       }
   }

}

int main() {
   int n,m,sum,k,id;//节点个数
   cin >> n >> m >> sum;
   for (int i = 0; i < n; i++) {
       cin >> vec[i];//得到每个节点的weight
   }
   int t;
   vector<vector<int> >chains(n);//存储树
   for (int i = 0; i < m; i++) {
       cin >> id >> k;
       for (int j = 0; j < k; j++) {//得到每个父节点的k个子节点
           cin >> t;
           chains[id].push_back(t);
       }
   }
   vector<vector<int> >output;//结果
   vector<int> path;//临时路径
   res.push_back(vec[0]);
   getsum(chains, 0, vec[0], sum,output,path);
      sort(output.begin(),output.end(),cmp); //得到正确的输出顺序
   for(int i =0;i<output.size();i++){
       for(int j = 0;j<output[i].size();j++){
           cout<<output[i][j];
           if(j<output[i].size()-1)cout<<" ";
       }
       cout<<endl;
   }

   return 0;
}

我是6J,爱吃爱玩爱笑的非典型程序~~~媛