Each input file contains one test case. Each case starts with a line containing 0 < N <= 100, the number of nodes in a tree, M (< N), the number of non-leaf nodes, and 0 < S < 230, the given weight number. The next line contains N positive numbers where Wi (<1000) corresponds to the tree node Ti. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID's of its children. For the sake of simplicity, let us fix the root ID to be 00.
For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.
Note: sequence {A1, A2, ..., An} is said to be greater than sequence {B1, B2, ..., Bm} if there exists 1 <= k < min{n, m} such that Ai = Bi for i=1, ... k, and Ak+1 > Bk+1.
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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=110;
struct node{
int weight;
vector<int> child;
}Node[maxn];
int n,m,theweight,tempweight=0,equalnum=0;
int father,childnum,child;
vector<int> temppath;
vector<vector<int> >ans;
bool 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 false;
}
void DFS(int now){
temppath.push_back(Node[now].weight);
tempweight+=Node[now].weight;
if(Node[now].child.size()==0){
if(tempweight==theweight) ans.push_back(temppath);
}
for(int i=0;i<Node[now].child.size();i++)
DFS(Node[now].child[i]);
temppath.pop_back();
tempweight-=Node[now].weight;
}
int main(){
cin>>n>>m>>theweight;
for(int i=0;i<n;i++)
cin>>Node[i].weight;
for(int i=0;i<m;i++){
cin>>father>>childnum;
for(int j=0;j<childnum;j++){
cin>>child;
Node[father].child.push_back(child);
}
}
DFS(0);
sort(ans.begin(),ans.end(),cmp);
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans[i].size();j++){
if(j!=ans[i].size()-1) cout<<ans[i][j]<<" ";
else cout<<ans[i][j]<<endl;
}
}
return 0;
}
n, m, s = map(int, input().split()) w = list(map(int, input().split())) tree = [[] for i in range(n)] for i in range(m): line = list(map(int, input().split())) tree[line[0]].extend(sorted(line[2:], key=lambda x:-w[x])) def dfs(i,cur,s,path): path.append(w[i]) cur += w[i] if not tree[i] and cur==s: print(' '.join(map(str,path))) for x in tree[i]: dfs(x,cur,s,path) path.pop(-1) path = [] dfs(0,0,s,path)
#include <iostream> #include <vector> #include <set> using namespace std; struct Node { int weight; vector<int> children; }; int N, M, S, sum; vector<Node> nodes; vector<int> path; multiset<vector<int> > allPath; void dfs(int root); int main() { ios::sync_with_stdio(false); // 读入数据 cin >> N >> M >> S; nodes.resize(N); for(int i=0; i<N; i++) { cin >> nodes[i].weight; } int id, K; for(int i=0; i<M; i++) { cin >> id >> K; nodes[id].children.resize(K); for(int j=0; j<K; j++) { cin >> nodes[id].children[j]; } } // 深搜找指定路径,输出结果 dfs(0); bool first; multiset<vector<int> >::reverse_iterator iter = allPath.rbegin(); for(;iter!=allPath.rend(); iter++) { path = *iter; first = true; for(int i=0; i<path.size(); i++) { if(first) { cout << path[i]; first = false; } else { cout << " " << path[i]; } } cout << endl; } return 0; } void dfs(int root) { sum += nodes[root].weight; path.push_back(nodes[root].weight); int numOfChildren = nodes[root].children.size(); if(numOfChildren) { for(int i=0; i<numOfChildren; i++) { dfs(nodes[root].children[i]); } } else { if(sum == S) { allPath.insert(path); } } sum -= nodes[root].weight; path.pop_back(); }
a = list(map(int,input().split())) m = dict(zip(map(lambda x:format(x,'02'),range(a[0])),map(int,input().split()))) d,r,n = {},[],set(m.keys()) for i in range(a[1]): b = input().split() n -= {b[0]} for i in b[2:]: d[i] = b[0] for i in n: p,q = m[i],[m[i]] while i in d: i = d[i] p += m[i] q.append(m[i]) if p == a[2]: r.append(q[::-1]) print('\n'.join(map(lambda x:' '.join(map(str,x)),sorted(r,reverse = True))))
#include<bits/stdc++.h> using namespace std; const int Max=110; int n,m,s,path[Max]; struct node { int data; vector<int> child; } Node[Max]; bool cmp(int x,int y){ return Node[x].data>Node[y].data; } void DFS(int index,int num,int sum) { if(sum>s) return ; if(sum==s) { if(Node[index].child.size()!=0) { return ; } for(int i=0; i<num; i++) { cout<<Node[path[i]].data; if(i<num-1) cout<<" "; else cout<<endl; } return ; } for(int i=0; i<Node[index].child.size(); i++) { int c=Node[index].child[i]; path[num]=c; DFS(c,num+1,sum+Node[c].data); } } int main() { while(cin>>n>>m>>s) { for(int i=0; i<n; i++) { cin>>Node[i].data; } int id,k; for(int i=0; i<m; i++) { cin>>id>>k; for(int j=0; j<k; j++) { int c; cin>>c; Node[id].child.push_back(c); } sort(Node[id].child.begin(),Node[id].child.end(),cmp); } path[0]=0; DFS(0,1,Node[0].data); } return 0; }
#include<bits/stdc++.h> using namespace std; const int max_size=105; typedef struct{ int weight; vector<int> childs; }node; node tree[max_size]; vector<string> vec; int k; void dfs(int v,int sum,string str){ if(tree[v].childs.size()==0){ str+=to_string(tree[v].weight); sum+=tree[v].weight; if(sum==k) vec.push_back(str); return; } sum+=tree[v].weight; str=str+to_string(tree[v].weight)+" "; for(int i=0;i<tree[v].childs.size();i++) dfs(tree[v].childs[i],sum,str); } bool comp(string a,string b){ if(a.compare(b)>0) return true; return false; } int main(){ int n,m,a_,b_,n_; cin>>n>>m>>k; for(int i=0;i<n;i++) cin>>tree[i].weight; for(int i=0;i<m;i++){ cin>>a_>>n_; for(int j=0;j<n_;j++){ cin>>b_; tree[a_].childs.push_back(b_); } } dfs(0,0,""); sort(vec.begin(),vec.end(),comp); for(int i=0;i<vec.size();i++) cout<<vec[i]<<endl; return 0; }PAT上测试案例2过不了,牛客提交全过了,这是为什么啊?
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <set> using namespace std; #define MAX 1005 #define _INF 10000009 int N, M, S; int W[MAX],t[MAX][MAX]; multiset<vector<int>> res; int visited[MAX]; void DFS() { fill(visited, visited + N + 10, false); int i, cnt = 0; vector<int>St, tempW; visited[0] = true; St.push_back(0); cnt += W[0]; while (!St.empty()) { i = St.back(); int w = 1; for (; w <= t[i][0]; ++w) { if (!visited[t[i][w]]) { visited[t[i][w]] = true; St.push_back(t[i][w]); cnt += W[t[i][w]]; break; } } if (t[i][0] == 0 || w > t[i][0]) { if (t[i][0] == 0 && cnt == S) { for (int m = 0; m < St.size(); ++m)tempW.push_back(W[St[m]]); res.insert(tempW); tempW.clear(); } visited[i] = true; St.pop_back(); cnt -= W[i]; } } } ; int main() { cin >> N >> M >> S; for (int i = 0; i < N; ++i)cin >> W[i]; int ID, K; for (int i = 0; i < N; ++i)fill(t[i], t[i] + N + 10, 0); for (int i = 0; i < M; ++i) { cin >> ID >> K; t[ID][0] = K; for (int j = 1; j <= K; ++j)cin >> t[ID][j]; } DFS(); vector<vector<int>> Tmp; vector<int> tt; for (auto i = res.begin(); i != res.end(); ++i) { Tmp.push_back(*i); } int size = Tmp.size(); for (int i = 0; i < size; ++i) { tt = Tmp.back(); Tmp.pop_back(); for (int j = 0; j < tt.size(); ++j) { cout << tt[j]; if (j < tt.size() - 1)cout << " "; } if (i < size - 1)cout << endl; } return 0; }
#include<iostream> (720)#include<vector> #include<algorithm> using namespace std; const int MAXN = 101; int N, M, S; int weights[MAXN] = { 0 }; vector<vector<int> >tree(MAXN); vector<vector<int> >answer; void dfs(int root, vector<int>path) { int sum = 0; path.push_back(root); for (int i = 0; i < path.size(); i++) { sum += weights[path[i]]; } if (sum == S&&tree[root].size()==0) { vector<int>tmp; for (int i = 0; i < path.size(); i++) { tmp.push_back(weights[path[i]]);//直接加对应权重 } answer.push_back(tmp); } else if (sum > S) { return; } else { for (int i = 0; i < tree[root].size(); i++) { vector<int>tmp = path; dfs(tree[root][i], tmp); } } } bool cmp(vector<int>a, vector<int>b) { int i = 0, j = 0; while (i < a.size() && j < b.size()) { if (a[i]!= b[j]) { return a[i]>b[j]; } i++; j++; } if (i != a.size()) { return true; } else if (j != b.size()) { return false; } return false; } int main() { cin >> N >> M >> S; for (int i = 0; i < N; i++) { cin >> weights[i]; } for (int i = 0; i < M; i++) { int id, num; cin >> id >> num; for (int j = 0; j < num; j++) { int child; cin >> child; tree[id].push_back(child); } } vector<int>t; dfs(0,t); sort(answer.begin(), answer.end(), cmp); for (int i = 0; i < answer.size(); i++) { for (int j = 0; j < answer[i].size(); j++) { if (j) { printf(" "); } printf("%d", answer[i][j]); } printf("\n"); } }
//Path of Equal Weight (30分) #include <iostream> (720)#include <vector> #include <algorithm> (831)#include <cstring> using namespace std; int n, m, s, weights[100], leaves[100], vis[100], weight = 0, in = 0; vector<int> arrays[100], lists[1000]; vector<int> temporary; vector<vector<int>> aa; bool comp(vector<int> a, vector<int> b) { int num = min(a.size(), b.size()); for (int i = 0; i < num; i++) { if (a[i] != b[i]) return a[i] > b[i]; } return a.size() > b.size(); } void dfs(int node) { vis[node] = 1; weight += weights[node]; temporary.push_back(weights[node]); if (weight == s && leaves[node] == 0) { lists[in] = temporary; in++; } if (weight < s) { for (int i = 0; i < leaves[node]; i++) { if (vis[arrays[node][i]] != 1) dfs(arrays[node][i]); } } weight -= weights[node]; temporary.pop_back(); } int main() { scanf("%d %d %d", &n, &m, &s); for (int i = 0; i < n; i++) scanf("%d", &weights[i]); memset(leaves, 0, sizeof(leaves)); memset(vis, 0, sizeof(vis)); for (int i = 0; i < m; i++) { int node, count; scanf("%d %d", &node, &count); leaves[node] = count; for (int j = 0; j < count; j++) { int leaf; scanf("%d", &leaf); arrays[node].push_back(leaf); } } dfs(0); for (int i = 0; i < in; i++) aa.push_back(lists[i]); sort(aa.begin(), aa.end(), comp); for (int i = 0; i < in; i++) { for (int j = 0; j < aa[i].size(); j++) { if (j == 0) printf("%d", aa[i][0]); else printf(" %d", aa[i][j]); } printf("\n"); } }
我的思路是从根节点深度搜索,用一个vector数组保存权值顺序,如果等于所给定的而且是叶子节点就压入vector数组中,注意一点就是不管是否成功都要回退
#include<iostream> #include<stdlib.h> #include<vector> #include<algorithm> const int N = 105; using namespace std; void DFS(int node); bool com(vector<int> a,vector<int> b) { return a > b; } vector<int> p[N],tem; vector<vector<int>> q; int n = 0, m = 0, s = 0, root = 0, num = 0,index = 0, sum = 0, w[N] = { 0 }; bool vis[N] = { false }; int main() { scanf("%d%d%d",&n,&m,&s); for (int i = 0; i < n; i++) {//输入权重 scanf("%d",&w[i]); } for (int i = 0; i < m;i++) { scanf("%d%d",&root,&num);//输入根节点和总的孩子节点个数 for (int j = 0 , x = 0; j < num; j++) {//把每个孩子压入栈中 scanf("%d",&x); p[root].push_back(x); } } DFS(0);//从根节点开始深度遍历 sort(q.begin(), q.end(),com);//按非递减的打印 for (int i = 0; i < q.size(); i++) { for (int j = 0; j < q[i].size(); j++) { printf("%d",q[i][j]); if (j != q[i].size()-1)printf(" "); } printf("\n"); } system("pause"); return 0; } void DFS(int node) { index++;//表示第n个节点,用于删除节点 vis[node] = true; tem.push_back(w[node]); sum += w[node]; if (sum == s&&p[node].size()==0) {//当权值等于m时并且该点为孩子节点,就把临时加入q中 q.push_back(tem); } for (int i = 0; i < p[node].size(); i++) {//深度遍历该节点的临界点 if (!vis[p[node][i]]) { DFS(p[node][i]); } } tem.erase(tem.begin()+index-1);//如果当前节点访问完没有满足条件就把该去掉该节点,并回退该点并且回退算术和还有点的个数 sum -= w[node]; index--; }
/*
https://www.nowcoder.com/questionTerminal/b3243680a9fb434da9f9b43122d9bc75
Path of Equal Weight (30) 2018-12-18
General mean: give you a tree and S, print all the paths from root to leaf that with weight S in non-increasing order.
Result: Though it is not a hard problem, It Cost me more than one hour. The context is long and the input-date is not small
so it is important to improve the speeh of reading the context and understant the question. In this code i have wast many
time on the bug that I mixed the variable such as I write tree[i].son[j] to tree[j].son[i], the more variable you have use
the more easily you might go worng. So if you variable is too long or many you have too many similar variable, do somthing
to improve the accuracy, and give a good name to avarible is a good ways.
*/
#include"stdafx.h"
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn = 110;
struct node{
int pre = -1;
int val = 0;
int sum = 0;
vector<int>son;
};
node tree[maxn];
int N, M, S;
void show(int i){
stack<int> id;
while (i != -1){
id.push(tree[i].val);
i = tree[i].pre;
}
while (!id.empty()){
cout << id.top();
id.pop();
if (!id.empty()) cout << " ";
}
cout << endl;
}
void run(int i){
if (tree[i].son.size() == 0 && tree[i].sum == S) show(i);
else if (tree[i].son.size() > 0){ // it node is not leaf node
for (int j = 0; j < tree[i].son.size(); j++){
int next = tree[i].son[j];
tree[next].sum = tree[i].sum + tree[next].val;
run(next);
}
}
}
int main(){
cin >> N >> M >> S;
for (int i = 0; i < N; i++) cin >> tree[i].val;
for (int id, k, t, i = 0; i < M; i++){
cin >> id >> k;
for (int j = 0; j < k; j++){
cin >> t;
tree[id].son.push_back(t);
tree[t].pre = id;
}
sort(tree[id].son.begin(), tree[id].son.end(), [](int a, int b){return tree[a].val > tree[b].val; });
}
tree[0].sum = tree[0].val;
run(0);
return 0;
}
#include <bits/stdc++.h> using namespace std; int main() { int n, m, s; cin >> n >> m >> s; vector<vector<int>> matrix(n, vector<int>(n, 0)); vector<int> weight(n, 0); set<int> root; for(int i = 0; i < n; ++i) cin >> weight[i]; for(int i = 0; i < m; ++i) { int begin, val, dst; cin >> begin >> val; root.insert(begin); for(int j = 0; j < val; ++j) { cin >> dst; matrix[dst][begin] = 1; } } vector<int> leaf; for(int i = 0; i < n; ++i) { if(root.find(i) == root.end()) { leaf.push_back(i); //cout << i << " "; } } vector<vector<int>> ans; for(auto v : leaf) { int val = 0; vector<int> tmp; queue<int> q; q.push(v); //cout << "v: " << v << " "; tmp.push_back(weight[v]); val += weight[v]; while(!q.empty()) { v = q.front(); q.pop(); for(int i = 0; i < matrix[v].size(); ++i) { if(matrix[v][i] == 1) { //cout << i << " "; q.push(i); tmp.push_back(weight[i]); val += weight[i]; break; } } } if(val == s) { reverse(tmp.begin(), tmp.end()); ans.push_back(tmp); } //cout << endl; } //sort ans auto cmp = [&](auto& a, auto& b)->bool { auto m = a.size() > b.size() ? b.size() : a.size() ; for(auto i = 0, j = 0; i < m && j < m; ++i, ++j) { if(a[i] > b[j]) return true; else if(a[i] == b[j]) continue; else return false; } return false; }; sort(ans.begin(), ans.end(), cmp); for(auto i = 0; i < ans.size(); ++i) { for(auto j = 0; j < ans[i].size(); ++j) { if(j+1 == ans[i].size()) cout << ans[i][j] << endl; else cout << ans[i][j] << " "; } } }
//dfs+回溯 #include <bits/stdc++.h> using namespace std; const int maxn=1e2+5; int n,m,s,w[maxn]; vector<int> son[maxn],vec; vector<vector<int> > path; void dfs(int rt,int sum){ sum+=w[rt];vec.push_back(w[rt]); if(sum>s) return ; int ok=1; for(int i=0;i<son[rt].size();++i){ int v=son[rt][i]; ok=0;dfs(v,sum);vec.pop_back(); } if(ok&&sum==s){ path.push_back(vec); } } int main(){ scanf("%d %d %d",&n,&m,&s); for(int i=0;i<n;++i) scanf("%d",&w[i]); for(int i=1,x,k;i<=m;++i){ scanf("%d %d",&x,&k); for(int j=1,tmp;j<=k;++j) scanf("%d",&tmp),son[x].push_back(tmp); } dfs(0,0); sort(path.begin(),path.end(),[](const vector<int> &x,const vector<int> &y){ return x>y;}); for(const auto &ch:path){ for(int i=0;i<ch.size();++i) if(i==0) printf("%d",ch[i]); else printf(" %d",ch[i]); printf("\n"); } return 0; }
N, M, St =list(map(int, input().split())) W =list(map(int, input().split())) T ={u:[] foru inrange(N)} P ={} # P[u] = v -- u(cur node) -> v(pre node) for_ inrange(M): l =list(map(int, input().split())) T[l[0]] ={u foru inl[2:]} fori inrange(l[1]): P[l[2:][i]] =l[0] root =0 defgetPathFromNode(node): end =node path =[] whileend !=root: path.append(end) end =P[end] path.append(root) returnpath[::-1] defdfs(G, root=root): Q, S =[(root, W[root])], set() #sum = [0] paths =[] whileQ: u, w =Q.pop() #print(u) ifu inS: continue S.add(u) #sum.append(sum[-1] + w) #if sum[-1] == S: ifw ==St andnotG[u]: paths.append(getPathFromNode(u)) forv inG[u]: Q.append((v, w+W[v])) returnpaths paths =dfs(T) # weights =[[W[j] forj ini] fori inpaths] weights =sorted(weights, key=lambdax:[x[i] fori inrange(min(len(j) forj inweights))], reverse=True) fori inweights: print(' '.join(map(str, i))) |
#include <cstdio> #include <vector> #include <set> using namespace std; const int maxn = 100 + 10; int weight[maxn], parent[maxn] = {-1}; vector<int> tree[maxn], road[maxn]; vector<int> SelectLeaf; multiset<vector<int> > allPath; int n, m, s; void DFS(int id, int tot){ if(!tree[id].size()){ tot += weight[id]; if(tot == s) SelectLeaf.push_back(id); return; } tot += weight[id]; for(unsigned int i = 0; i<tree[id].size(); i++){ DFS(tree[id][i], tot); } } void Show_Road(int node, int iter){ if(node == -1) return; else{ Show_Road(parent[node], iter); // if(node == 0) printf("%d", weight[node]); // else printf(" %d", weight[node]); road[iter].push_back(weight[node]); } } int main(){ scanf("%d %d %d", &n, &m, &s); for(int i=0; i<n; i++) scanf("%d", &weight[i]); for(int i=0; i<m; i++){ int u, num; scanf("%d %d", &u, &num); for(int j=0; j<num; j++){ int v; scanf("%d", &v); tree[u].push_back(v); parent[v] = u; } } DFS(0, 0); for(unsigned int i=0; i<SelectLeaf.size(); i++){ int leaf = SelectLeaf[i]; Show_Road(leaf, i); allPath.insert(road[i]); } for(auto iter = allPath.crbegin(); iter!=allPath.crend(); iter++){ auto path = *iter; for(unsigned int i=0; i<path.size(); i++){ printf("%d", path[i]); if(i!=path.size()-1) printf(" "); } printf("\n"); } return 0; }
来自鄙人博客http://blog.csdn.net/sinat_29278271
# include <iostream> # include <vector> # include <algorithm> using namespace std; struct Node { int weight; vector<int> edge; int child; Node():child(0){} bool operator < (const Node& cmper) const { return weight > cmper.weight; } }; Node v[101]; bool cmper(int a,int b) { return v[a] < v[b]; } void PrintPath(vector<int>& path) { vector<int>::iterator it; for (it = path.begin();it!=path.end();it++) printf("%d%c",*it,it+1==path.end()?'\n':' '); } void dfs(int loca,int rest,vector<int>& path) {//cout << "loca = " << loca << endl; Node& cur = v[loca]; path.push_back(cur.weight); rest -= cur.weight; if (rest==0&&cur.child==0) PrintPath(path); else { vector<int>:: iterator it; for (it = cur.edge.begin();it!=cur.edge.end();it++) dfs(*it,rest,path); } path.pop_back(); } int main() { int i,j,k,root,temp; int n,m,s; cin >> n >> m >> s; for (i=0;i<n;i++) cin >> v[i].weight; for (i=0;i<m;i++) { cin >> root >> k; while (k--) { cin >> temp; v[root].edge.push_back(temp); } v[root].child = k; } for (i=0;i<n;i++) sort(v[i].edge.begin(),v[i].edge.end(),cmper); vector<int> path; dfs(0,s,path); return 0; }
void dfs(int s){
int i,next;
if(res==S){
if(child[s]==0){
cout<<weight[0];
for(i=0;i<solution.size();i++){
cout<<" "<<solution[i];
}
cout<<endl;
}
return ;
}
for(i=0;i<child[s];i++){
if(!visited[nodes[s][i]]){
visited[nodes[s][i]]=1;
res+=weight[nodes[s][i]];
solution.push_back(weight[nodes[s][i]]);
dfs(nodes[s][i]);
visited[nodes[s][i]]=0;
res-=weight[nodes[s][i]];
solution.pop_back();
}
}
}