首页 > 试题广场 >

Path of Equal Weight (30)

[编程题]Path of Equal Weight (30)
  • 热度指数：1731 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti . The weight of a path from R to L is defined to be the sum of the weights of all the nodes along the path from R to any leaf node L.
Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let's consider the tree showed in Figure 1: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in Figure 1.


Figure 1

输入描述:
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.
示例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
算法知识视频讲解
添加回答
曹冠杰头像 曹冠杰
其实不用深搜也不用广搜，在输入的时候直接标记所有的叶子节点，然后对每个节点设置一个父指针。最后对于所有的叶子节点，根据他的父指针从下向上累加，把所有符合条件的节点保存下来，然后排一下序输出！
发表于 2016-11-20 14:16:01 回复(1)
Myhui头像 Myhui 
#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;
}

发表于 2019-01-18 18:13:25 回复(0)
袁博文202头像 袁博文202 
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)

发表于 2018-04-19 22:43:29 回复(0)
啥头像 啥
总体思路：
        1.找出所有符合要求的路径。    用深搜可以遍历。
        2.结果按照非升序输出。   用multiset来存住所有符合要求的路径，自动排序，反序输出即可。

代码如下： 
#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();
}


发表于 2015-12-15 09:49:09 回复(0)
初心者托奇头像 初心者托奇 
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))))

发表于 2020-03-03 10:40:01 回复(0)
MniQ头像 MniQ
//这题限制少，结点才100个，所以简单。
//在pat30分题里算水的了。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <map>
using namespace std;

//1053 Path of Equal Weight
//n叉树，根节点00，其他结点编号[01,99]
//用int存储编号节约空间
//输出要求按权重降序，因此输入的时候可以先进行一次排序。

class node {
public:
    int id;
    int n_children;
    int *children;
};

int n, m, w;
long long s;//<=2^30

map<int,node> mp;
vector<long long> weights;
vector<vector<int> > tgt;

void dfs(int start,long long sum_w, vector<int> path) {
    
    path.push_back(start);
    long long cur_sum = sum_w + weights[start];

    if (mp.find(start) == mp.end()) {
        //来到了叶子结点
        if (cur_sum == s){
            tgt.push_back(path);
        }
        return;
    }

    //非叶子结点，继续往下
    node cur_ = mp[start];
    //因为结果要求降序，所以从权重较大结点开始dfs。
    for (int i = cur_.n_children-1; i >=0 ; --i) {
        int cur_c = cur_.children[i];
        dfs(cur_c, cur_sum, path);
    }
    return;
}


bool weight_cmp(const int a, const int b) {
    return weights[a] < weights[b];
}

int main() {

    cin >> n >> m >> s;

    for (int i = 0; i < n; ++i) {
        cin >> w;
        weights.push_back(w);
    }

    int id, k,child;
    for (int i = 0; i < m; ++i) {
        cin >> id >>k;
        int *p = new int[k];
        for (int j = 0; j < k; ++j) {
            cin >> child;
            p[j] = child;
        }
        //为了保证结果是降序的，此处需要对子结点按权重升序
        sort(p, p + k, weight_cmp);
        mp[id]={id,k,p};
    }

    vector<int> t;
    dfs(0, 0, t);

    for (int i = 0, l = tgt.size(); i < l; ++i) {
        t = tgt[i];
        cout << weights[t[0]];
        for (int j=1, lj = t.size(); j < lj; ++j) {
            cout << " "<<weights[t[j]];
        }
        cout << endl;
    }

    return 0;
}

发表于 2019-08-15 11:37:57 回复(0)
C/C++
猫猫猫1头像 猫猫猫1 
#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;
}


发表于 2022-10-29 20:01:37 回复(5)
LR我又馋了头像 LR我又馋了 
#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过不了，牛客提交全过了，这是为什么啊？
发表于 2021-08-18 23:14:08 回复(0)
Xtion头像 Xtion 
#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;
}


发表于 2020-12-04 16:35:39 回复(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");
	}
}


发表于 2020-03-27 00:27:41 回复(0)
再不中奖就吃屎头像 再不中奖就吃屎 
//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");
    }
}

发表于 2020-03-25 18:28:20 回复(0)
gangstar头像 gangstar

我的思路是从根节点深度搜索，用一个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--;
}
发表于 2019-10-24 21:36:22 回复(0)
C/C++
BlackCarDriver头像 BlackCarDriver

/*
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;
}

发表于 2018-12-18 14:38:20 回复(0)
中年失业头像 中年失业
这题恶心极了，提交的时候明明写的clang，结果报错提醒是gcc， 同版本的gcc都没报错，我佛了
最后还是ac了 

#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] << " ";
        }
    }
}

编辑于 2018-11-15 20:02:26 回复(0)
C/C++
OFShare头像 OFShare 
//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;
} 

发表于 2018-03-17 00:38:50 回复(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)))
发表于 2018-03-13 15:40:58 回复(0)
RicardoZi头像 RicardoZi 
#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;
}

发表于 2017-09-06 16:53:35 回复(0)
多情应笑我头像 多情应笑我
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn = 110;
struct Node {
    int weight;
    vector<int> child;
}node[maxn];
bool cmp(int a, int b) {
    return node[a].weight > node[b].weight;
}
vector<int> ans[maxn], temp;
int tempSum = 0, ansNum = 0;
int n, m, s;
void DFS(int index, int tempSum, vector<int> temp) {
    if (node[index].child.size() == 0 && node[index].weight + tempSum == s) {
        temp.push_back(node[index].weight);
        ans[ansNum++] = temp;
        return;
    }
    if (node[index].weight + tempSum < s) {
        temp.push_back(node[index].weight);
        tempSum = node[index].weight + tempSum;
        for (int i = 0; i < node[index].child.size(); ++i) DFS(node[index].child[i], tempSum, temp);
    }
}
int main() {


    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &node[i].weight);
    }
    for (int i = 0; i < m; ++i) {
        int id, childNum, childId;
        scanf("%d%d", &id, &childNum);
        for (int j = 0; j < childNum; ++j) {
            scanf("%d", &childId);
            node[id].child.push_back(childId);
        }
        sort(node[id].child.begin(), node[id].child.end(), cmp);
    }
    DFS(0, tempSum, temp);
    for (int i = 0; i < ansNum; ++i) {
        for (int j = 0; j < ans[i].size(); ++j) {
            printf("%d", ans[i][j]);
            if (j < ans[i].size() - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

发表于 2017-03-29 14:22:32 回复(0)
算法妙妙屋头像 算法妙妙屋 
来自鄙人博客http://blog.csdn.net/sinat_29278271
     今天被一道PAT顶级的题目折腾哭了，还好总算是做出来了，决定睡前还是发一篇博客吧，好久没写题解了，顶级的那道我明天再扯。
     这道题目其实水的很，要是我考甲级的时候30分的题目是这个，我做梦都会笑出来的。要说算法，其实根本没有算法，从顶点开始暴搜就好了，无需剪枝一路搜到叶子，如果到叶子的时候发现权重与题目要求的相符，就输出路径，为了维护字典序对每个节点的孩子进行一次排序，这样搜索的路径自动遵循字典序从小到大的原则。，然后，然后就没有什么了。 
# 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;
}

     
发表于 2015-09-04 18:58:58 回复(0)
newcomer头像 newcomer
本题 考察深度优先搜索。
给定一个数值，要求输出这棵树中所有等于此值的路径，按照非增顺序输出。
在输入一个非叶节点之后，将它的孩子节点按照权重非递增顺序排序；
然后深度优先搜索，如果在某个叶节点处路径的权重等于给定数值，则输出此路径。 
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();
		}
	}
}


编辑于 2015-07-05 21:22:57 回复(0)
提交观点

问题信息

穷举 递归
难度：
20条回答 12553浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号