PAT 1053

题目 ： Path of Equal Weight

分值 ： 30
难度 ： 中等题
思路 ： 做过两遍这个题，第一次做遍历叶结点，从下往上，看满不满足条件； 第二次做DFS+回溯
坑点 ： 两者都有一个 涉及多条路径存储问题
评语 ： 记录下各个点的数据信息，然后无论DFS也好，自下而上也好，想到一种方法遍历所有从头
       到底的路径即可。

遍历所有的叶子结点，自下而上求和，具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include "stdio.h"
#include "stdlib.h"
int result[100][100];
int cmp(const void *a , const void* b)
{
    int count = -1 ;
    while( ((int*)a)[++count] == ((int*)b)[count] );
    return  ((int*)b)[count] - ((int*)a)[count];
}
int main() {
    int N , K ,target ;
    scanf("%d%d%d" , &N , &K,&target);
    int value[N] ;
    int f[N] ;
    int flag[N] ;
    for(int i = 0 ; i<N ; i++)
    {
        flag[i] = 0 ;
        scanf("%d" , &value[i]) ;
    }
    for(int i = 0; i< K ; i++)
    {
        int father , sum ;
        int temp ;
        scanf("%d%d",&father ,&sum);
        flag[father] = 1 ;
        for(int j = 0 ; j < sum ; j++)
        {
            scanf("%d" ,&temp) ;
            f[temp] = father ;
        }
    }
    f[0] = -1 ;
    int path[N][N] ;
    int result_ = 0 ;
    int index[N]  ;
    int count =0 ;
    for(int i = 0 ; i< N ;i++)
        for(int j = 0 ; j<N ;j++)
            path[i][j] = 0 ;
    for(int i = 0 ; i< N ; i++)
    {
        int total= 0 ;
        index[i] = 0 ;
        if(flag[i])
            continue;
        for(int j = i ; f[j]!= -1 ; j= f[j])
        {
            path[i][index[i]++] = j ;
            total += value[j];
        }
        path[i][index[i]++] = 0 ;
        total += value[0] ;
        if(total == target )
        {
            count ++  ;
            int cur = 0 ;
            for(int k = index[i] -1 ; k>=0 ; k--)
            {
                result[result_][cur] = value[ path[i][k]] ;
                cur ++ ;
            }
            result_++ ;
        }
    }
    qsort(result , result_ , sizeof(result[0]) , cmp);
    for(int i = 0 ; i< result_ ; i++)
    {
        printf("%d" , result[i][0]) ;
        for(int j = 1 ; result[i][j]!=0 ; j++)
            printf(" %d",result[i][j] );
        printf("\n");
    }
}

DFS+回溯 具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector< vector<int> > path ;
vector< vector<int> >::iterator iter ;
vector <int > ::iterator iter1 ;
int value[1001] ;
int map[1001][1001] ;
int flag[1001 ] ;
int N , M ,S;
int sum = 0 ;
int leave[1001] ;

vector<int > temp ;
bool cmp(vector<int> a  , vector<int > b )
{
    int cur = 0 ;
    int min = a.size() > b.size() ? b.size() :a.size() ;
    while(a[cur] == b[cur] && cur< min ) cur++;
    return a[cur] > b[cur] ;
}

void dfs(int x){
    if(flag[x])
        return ;
    flag[x] = 1 ;
    sum+= value[x] ;
    temp.push_back(value[x]) ;
    int xx = sum ;
    if(sum==S && !leave[x])
    {
        path.push_back(temp);    // 将结果直接 存到 path中
        sum -= value[x] ;
        temp.pop_back() ;          // 返回
        flag[x] = 0 ;
        return ;
    }
    if(sum >S)
    {
        sum -= value[x] ;
        temp.pop_back() ;
        flag[x] = 0 ;
        return ;
    }
    for(int i = 0 ; i<N ; i++)
    {
        if(map[x][i] ) dfs(i) ;
    }
    sum -= value[x];
    temp.pop_back();
    flag[x] = 0 ;
    return ;
}

int main() {
    cin >> N >>M>>S ;
    for(int i = 0 ; i< N ; i++)
        cin >>value[i] ;
    for(int i = 0 ; i < M ; i++)
    {
        int id , temp ;
        cin >> id >> temp ;
        leave[id] =1 ;
        for(int j = 0 ; j < temp ; j++)
        {
            int son ;
            cin >> son ;
            map[id][son]= 1 ;
        }
    }
    dfs(0);
    sort(path.begin() , path.end() , cmp ) ;
    for(iter = path.begin() ; iter!=path.end() ; iter++)
    {
        for(iter1 = iter->begin() ; iter1 != iter->end() ; iter1++)
        {
            if(iter1!=iter->begin())
                cout<<" " ;
            cout << *iter1 ;
        }
        cout <<endl ;
    }
}