PAT甲级1053.

目录

A1053

题目

样例

输入:

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

思路和坑点

　　使用树的dfs和回说剪枝来实现统计要求的路径。其中为了输出路径时按照规则从大到小，对每个结点的孩子都按照权重从大到小排列。也可以把每个符合要求的路径保存，并按照要求排序，最后统一输出。

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node{                                //使用结构体存放结点 
    int weight;                                //权值 
    vector<int> child;                        //孩子结点使用数组表示 
}Node[105];                                    //存放所有的结点，最多100个结点 
int n,m,s;
vector<int> path;                            //存放路径 

bool cmp(int a,int b){                        //将孩子每一层按照权值从大到小排序，这样dfs的结果才能满足路径权值从大到小 
    return Node[a].weight>Node[b].weight;
}                                            //（也可以将所有的路径保存后排序输出 ） 
void DFS(int index,int sum);            
int main(void)
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<n;i++)
        scanf("%d",&Node[i].weight);
    int id,k,child;
    for(int i=0;i<m;i++){
        scanf("%d%d",&id,&k);
        for(int j=0;j<k;j++){
            scanf("%d",&child);
            Node[id].child.push_back(child);
        }
        sort(Node[id].child.begin(),Node[id].child.end(),cmp);    //孩子读取完即排序 
    }
    path.push_back(0);
    DFS(0,Node[0].weight); 
    
    return 0;
} 
void DFS(int index,int sum)
{
    if(sum>s) return;                            //如果路径上的和大于s，不满足规则，返回 
    else if(sum==s){
        if(Node[index].child.size()!=0) return;//说明该结点不是叶子结点，不满足题目要求，直接返回，否则输出路径
        else{
            for(int i=0;i<path.size();i++){
                if(i) putchar(' ');
                printf("%d",Node[path[i]].weight);
            }
            putchar('\n');
            return;
        } 
    }
    else{                                        //否则对其所有孩子递归dfs 
        for(int i=0;i<Node[index].child.size();i++){
            int child=Node[index].child[i];
            path.push_back(child);                //当前结点算入路径 
            DFS(child,sum+Node[child].weight);    //当前孩子的递归dfs结束后，要从路径中删除，以继续进行下一个孩子的dfs 
            path.pop_back();
        }
    }
}