邻接表还是挺方便的,之前y其他题目也是用邻接表讲的。如果有需要可以参阅笔者的ac代码。
注:思路还是这个思路,dfs变成邻接表版本的而已。
这是笔者的PAT题解笔记
https://blog.csdn.net/shizheng_li/category_10745055.html
有兴趣的大佬可以移步。如果给点个赞、评论一下最好不过了。在此谢过各位了啦。
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n , m,S;
//邻接表
int h[N],e[N],ne[N],idx;
int w[N]; //权重
vector<vector<int>> ans; //记录路径
//add函数:邻接表加边
// e[i]存的是当前结点
//ne[i] 存的是单链表中下一个结点“序号”
//idx 就是单链表中的“序号”
void add(int a, int b){
e[idx] =b, ne[idx]= h[a],h[a] =idx ++;
}
/*
暴搜所有等于S的路径
u:当前结点
s:权值
path:路径
*/
void dfs(int u,int s , vector<int>& path){
//递归结束条件
if(h[u] == -1){ // 是叶子结点
if(s == S) {
ans.push_back(path);
return;
}
}
//暴搜u的所有儿子
for(int i=h[u]; i!= -1 ;i=ne[i]){
path.push_back(w[e[i]]); //更新路径
dfs(e[i],s+w[e[i]],path); //暴搜下一个点
path.pop_back(); //恢复现场
}
}
int main(){
memset(h, -1, sizeof h);
cin>> n >> m >> S;
for(int i = 0; i < n; i++) cin>>w[i];//i号结点的权重是w[i]
while(m--){
int id , n1;
cin>> id >> n1;
while(n1--){ //id结点的儿子们
int son;
cin >> son;
add(id ,son);
}
}
//根结点
int root = 0;
//初始化路径为根结点
vector<int> path({w[0]});
//暴搜
dfs(root,w[0],path);
//排序
sort(ans.begin(),ans.end(),greater<vector<int>>());
//输出
for(auto p :ans){
cout<<p[0];
for(int i=1;i<p.size();i++) cout<<" "<<p[i];
cout<<endl;
}
}
path.push_back(w[e[i]]); 放到循环外可以嘛,
没看懂你的问题
h[]数组是做什么的
h[]数组是做什么的