求总权重结果不正确

编程追风梦小号

如题，可运行，但是结果一直是10
正确的应该是x出现两次后被两个父节点共享，应该是20
但是一直找不到原因........

1. #include <iostream>
   
2. #include <vector>
   
3. #include <memory>
   
4. #include <functional>
   
5. #include <unordered_map>
   
6. #include <string>
   
7. #include <algorithm>
   
8. 
   
9. template<typename T>
   
10. class Registry {
    
11.     std::unordered_map<std::string, std::function<T(const std::vector<std::string>&)>> creators;
    
12. public:
    
13.     void add(const std::string& key, std::function<T(const std::vector<std::string>&)> fn) {
    
14.         creators[key] = fn;
    
15.     }
    
16.     T create(const std::string& key, const std::vector<std::string>& args) {
    
17.         auto it = creators.find(key);
    
18.         if (it == creators.end()) throw std::runtime_error("not found: " + key);
    
19.         return it->second(args);
    
20.     }
    
21. };
    
22. 
    
23. struct Node {
    
24.     std::string name;
    
25.     std::vector<std::shared_ptr<Node>> children;
    
26.     int weight;
    
27.     Node(std::string n, int w) : name(std::move(n)), weight(w) {}
    
28. };
    
29. 
    
30. class Builder {
    
31.     Registry<std::shared_ptr<Node>> reg;
    
32.     std::unordered_map<std::string, std::shared_ptr<Node>> pool;
    
33. public:
    
34.     Builder() {
    
35.         reg.add("leaf", [](const std::vector<std::string>& a) {
    
36.             return std::make_shared<Node>(a[0], std::stoi(a[1]));
    
37.         });
    
38.         reg.add("group", [](const std::vector<std::string>& a) {
    
39.             return std::make_shared<Node>(a[0], 0);
    
40.         });
    
41.     }
    
42.     std::shared_ptr<Node> make(const std::string& type, const std::vector<std::string>& args) {
    
43.         auto n = reg.create(type, args);
    
44.         pool[n->name] = n;
    
45.         return n;
    
46.     }
    
47.     std::shared_ptr<Node> get(const std::string& name) {
    
48.         auto it = pool.find(name);
    
49.         return it == pool.end() ? nullptr : it->second;
    
50.     }
    
51.     void link(const std::string& parent, const std::string& child) {
    
52.         auto p = get(parent);
    
53.         auto c = get(child);
    
54.         if (p && c) p->children.push_back(c);
    
55.     }
    
56. };
    
57. 
    
58. int computeWeight(const std::shared_ptr<Node>& node, std::vector<std::string>& visited) {
    
59.     if (!node) return 0;
    
60.     if (std::find(visited.begin(), visited.end(), node->name) != visited.end())
    
61.         return 0;
    
62.     visited.push_back(node->name);
    
63.     int total = node->weight;
    
64.     for (auto& c : node->children) {
    
65.         total += computeWeight(c, visited);
    
66.     }
    
67.     return total;
    
68. }
    
69. 
    
70. int main() {
    
71.     Builder b;
    
72.     b.make("leaf", {"x", "10"});
    
73.     b.make("group", {"left", "0"});
    
74.     b.make("group", {"right", "0"});
    
75.     b.make("group", {"root", "0"});
    
76.     b.link("root", "left");
    
77.     b.link("root", "right");
    
78.     b.link("left", "x");
    
79.     b.link("right", "x");
    
80. 
    
81.     std::vector<std::string> visited;
    
82.     auto root = b.get("root");
    
83.     int result = computeWeight(root, visited);
    
84. 
    
85.     std::cout << result << std::endl;
    
86.     return 0;
    
87. }

复制代码

FishC

原因很明确：你的 visited 是“全局累积”的，不是“当前路径”。

遍历完 left 分支后，x 已经留在 visited 里了；等遍历 right 分支再遇到 x 时，就直接返回 0，所以只算了 10。

visited 的本意应该是防止“环”导致无限递归，所以它只需要记录**当前递归路径上**的节点。递归返回前把它弹出来（回溯）即可：

1. 
   
2. int computeWeight(const std::shared_ptr<Node>& node, std::vector<std::string>& path) {
   
3.     if (!node) return 0;
   
4.     // 只有出现在“当前路径”上，才说明成环
   
5.     if (std::find(path.begin(), path.end(), node->name) != path.end())
   
6.         return 0;
   
7. 
   
8.     path.push_back(node->name);
   
9.     int total = node->weight;
   
10.     for (auto& c : node->children) {
    
11.         total += computeWeight(c, path);
    
12.     }
    
13.     path.pop_back();   // 关键：离开该节点时移除，允许别的分支再次访问
    
14.     return total;
    
15. }
    

复制代码

这样 x 会在 left 路径里算一次、在 right 路径里再算一次，结果就是 20；而真正成环时依然会被截断。

补充一点：用 name 判环有个隐患——不同节点同名会误判。更严谨的写法是按节点地址判断，比如把 path 换成 std::vector<const Node*>&，比较 node.get()。另外你贴的代码里 pool = n 应该是 pool[key] = n，std::function 的模板参数和 make_shared 的参数也被论坛吞掉了一些，注意别照抄。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

青出于蓝

啊 bro真的是编程追风梦吗？？
老乡见老乡 两眼泪汪汪 qaq

编程追风梦小号

青出于蓝 发表于 2026-10-18 21:02
啊 bro真的是编程追风梦吗？？
老乡见老乡 两眼泪汪汪 qaq

是的呀，追风梦被c++难哭了走头无路想起来还有鱼C这个网站

青出于蓝

编程追风梦小号 发表于 2026-10-19 18:14
是的呀，追风梦被c++难哭了走头无路想起来还有鱼C这个网站

我都是先想起来deepseek

青出于蓝

编程追风梦小号 发表于 2026-10-19 18:14
是的呀，追风梦被c++难哭了走头无路想起来还有鱼C这个网站

你们是不是都不知道deepseek

编程追风梦小号

青出于蓝 发表于 2026-10-19 21:53
你们是不是都不知道deepseek

其实知道的哈哈哈但是都用chatgpt