1053 Path of Equal Weight

题目描述
解题思路：没什么好说，就是深搜。

#include
#include
#include
#include
using namespace std;
const int N = 1e5+10;
int h[N],e[N],ne[N],idx;
void add(int a,int b){
    ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}
int n,m,w,weights[N],vis[N],cnt;
vector<int>res[N],tem_path;
string tem_sort[N];
int cur_weights = 0;
void dfs(int u){
    tem_path.push_back(weights[u]);
    cur_weights += weights[u];
    if(h[u] == -1){
        if(cur_weights == w)
            res[cnt++] = tem_path;
        return;
    }
    for(int i = h[u];i != -1;i = ne[i]){
        int p = e[i];
        if(!vis[p]){
            vis[p] = 1;
            dfs(p);
            vis[p] = 0;
            cur_weights -= weights[p];
            tem_path.pop_back();
        }
    }
}
int main(){
    cin>>n>>m>>w;
    memset(h,-1,sizeof h);
    for(int i = 0;i < n;i++) cin>>weights[i];
    for(int i = 0;i < m;i++){
        int a,b,num;
        scanf("%d %d",&a,&num);
        for(int j = 0;j < num;j++){
            scanf("%d",&b);
            add(a,b);
        }
    }
    dfs(0);
    sort(res,res+cnt);
    for(int i = cnt-1;i >= 0;i--){
        for(int j = 0;j < res[i].size();j++){
            if(j != res[i].size() - 1)
                printf("%d ",res[i][j]);
            else printf("%d",res[i][j]);
        }
        cout<<endl;
    }
    return 0;
}
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