写一个菜鸡版本的吧。

#include <cstdio>
#include<iostream>
#include <bits/stdc++.h>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<string, int> weight;
unordered_map<string, vector<string>> mp;

int m;
int n;
int cap;

string ans;
int num = 0;
bool isOverflow = false;


void dfs(string start, int cost, vector<string> &callOrder) {
    cout << endl;
    // 已经栈溢出了，后续都不用执行了
    if(isOverflow) {
        return;
    }
    // 栈空间消耗没了或者没有继续往下调用了
    if(cost > cap) {
        isOverflow = true;
        num = cost;
        // 保存当前的调用关系
        int csize = callOrder.size();
        if(csize > 0) {
            ans = "";
            for(int i = 0; i < csize - 1; i++) {
                ans += callOrder[i] + '-';
            }
            ans += callOrder[csize - 1];
        }
        return;
    }
    
    // 没有继续调用了
    if(mp.count(start) == 0) {
        if(cost > num) {
            num = cost;
            int csize = callOrder.size();
            if(csize > 0) {
                ans = "";
                for(int i = 0; i < csize - 1; i++) {
                    ans += callOrder[i] + '-';
                }
                ans += callOrder[csize - 1];
            }
            
        }
        return;
    }

    // 执行当前的调用关系
    for(auto& item:mp[start]){
        cost += weight[item];
        callOrder.push_back(item);
        dfs(item, cost, callOrder);
        cost -= weight[item];
        callOrder.pop_back();

        // 栈溢出了
        if (isOverflow) {
            return;
        }
    }
}


int main() {
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        string temp;
        int w;
        cin >> temp >> w;
        weight[temp] = w;
    }

    cin >> m;
    string start;
    for(int i = 0; i < m; i++) {

        string temp;
        cin >> temp;
        if(i == 0) start = temp;

        string line;
        getline(cin, line);
        istringstream iss(line);
    
        string next;
        while (iss >> next) {
            mp[temp].push_back(next);
        }
    }

    cin >> cap;
    vector<string> callOrder = {start};
    dfs(start, weight[start], callOrder);
    if(isOverflow) {
        cout << "true";
    } else {
        cout << "false";
    }
    cout <<  " " << ans << " " << num;
    return 0;
}

恕我直言，塔子哥的题解感觉都太丑陋了、、 当然，我写的也挺丑陋的T_T 本题没什么好说的，思路很简单，对依赖树深度遍历，遍历图中计算当前路径权值和，超出则退出。就是写起来有点麻烦，但是写出来不容易错。

#include "bits/stdc++.h"
using namespace std;

struct Node{//树的节点
    char name;
    int val;
    vector<struct Node*> child;
};

vector<Node*> stk;//名作栈，实际上是vector（方便求和、输出）
vector<char> maxproc;//记录了当前为止权值最大的路径
int tot,Max = 0;//tot:阈值，Max：当前最大权值

int sum(){//求当前权值
    int re = 0;
    for(auto&x:stk)
        re += x->val;
    return re;
}

void printmaxproc(){//打印最大权值路径
    for(int i =0;i<(int)maxproc.size();i++){
        if(i)
            cout<<'-';
        cout<<maxproc[i];
    }
    cout<<" ";
}

void end(char flag){//输出函数
    if(!flag)
        cout<<"false ";
    else cout<<"true ";
    printmaxproc();
    cout<<Max;
    exit(0);
}

void proc(Node* x){//DFS函数，先判断权值和，再对当前节点每个子节点访问
    for(auto& it:x->child){
        stk.push_back(it);
        int cost = sum();
        if(cost > Max){
            Max = cost;
            maxproc.clear();
            for(int i = 0;i<(int)stk.size();i++){
                maxproc.push_back(stk[i]->name);
            }
        }
        if(Max > tot)
            end(1);//溢出退出
        proc(it);
    }
    stk.pop_back();
}

int main(){
    int n;
    cin>>n;
    map<char, Node*> nodes;//储存了名称->节点，方便使用
    for(int i=0;i<n;i++){//建立节点
        char name;
        int val;
        cin>>name>>val;
        Node* temp = new Node;
        temp->name = name;
        temp->val = val;
        nodes[name] = temp;
    }
    
    int m;
    cin>>m;
    char Main;
    for(int i=0;i<m;i++){//建立父子关系，注意对行的处理
        char f = getchar();
        while(f < 'A' || f > 'Z') f = getchar();
        if(!i) Main = f;//函数入口
        char c = '0';
        while((c = getchar()) != '\n'){
            if(c <= 'Z' && c >= 'A'){
                nodes[f]->child.push_back(nodes[c]);
            }
        }
    }

    stk.push_back(nodes[Main]);//从Main函数开始调用

    cin>>tot;
    proc(nodes[Main]);//DFS调用
    end(0);//正常退出
}

题面描述

在程序运行过程中，函数调用可能导致栈溢出。给定函数的栈大小和调用关系，判断程序是否会发生栈溢出，并输出相关信息，包括是否溢出、触发溢出的调用路径（如果有）、以及栈的最大消耗。如果没有溢出，则输出最大栈消耗的调用路径。输入包括函数数量、每个函数的栈大小、调用关系和系统最大栈空间，输出需提供三项信息，确保正确识别栈的使用情况。

思路

简化来说，这个问题本质上是一个有向无环图（DAG）中的路径最大权值问题，主要关注的是如何判断路径的栈消耗是否超过系统允许的最大空间。

1. 图结构与路径搜索：

   • 这个问题可以看作是从入口函数出发的一种路径搜索问题，其中每条路径代表一个调用链。
   • 图中每个节点（函数）有一个权值（栈大小），而路径上的累加权值即为路径的总栈消耗。
   • 关键是找到所有从入口到叶子的调用路径，并计算其栈消耗。

2. 栈溢出的检测条件：

   • 对于每条路径，计算其栈消耗并与系统最大栈空间进行比较。
   • 如果某条路径上的栈消耗超过系统配置的最大栈空间，则认为出现了栈溢出，且只需找到第一条导致栈溢出的路径即可，因为后续路径已经无关紧要。

3. 最大栈消耗路径：

   • 如果不存在栈溢出，则我们要寻找占用最大栈空间的路径（路径栈消耗最高的路径），这就需要记录所有路径的栈消耗值，并返回其中最大的一条。
   • 这种情况下，我们找到的就是调用链中消耗栈空间最多的一条路径。

4. 无递归的简化：

   • 由于题目保证没有递归调用，所以它是一个DAG，这使得问题在递归遍历过程中不会进入死循环，能顺利完成所有路径的计算。

具体分析

完整思路

1. 解析输入数据：

   • 首先我们读取输入的函数数量及每个函数对应的栈大小。这一步的目的是将每个函数的栈消耗大小映射到一个字典或哈希表中（如 C++ 中的 unordered_map 或 Java 中的 HashMap）。
   • 然后，我们读取函数的调用关系，将这些调用关系表示为有向图。图的结构可以通过邻接表的形式存储，使用字典，键为调用函数，值为其调用的子函数列表。

2. 构建调用图：

   • 每个函数的调用关系表示为有向边（调用方到被调用方）。例如，如果函数 A 调用了 B 和 C，则会有两条边：A->B 和 A->C。
   • 需要特别注意调用顺序和递归问题。题目中已经说明不会有递归调用，所以不需要检测图中的环，处理有向无环图（DAG）即可。

3. 深度优先搜索 (DFS)：

   • 起点：从主函数开始，进行深度优先遍历。主函数可以通过读取调用关系的第一个函数作为入口点。
   • 状态跟踪：在遍历过程中，我们需要跟踪当前栈空间的使用情况，以及当前的调用路径。
     • 对每个函数调用时，将当前函数的栈大小累加到当前栈空间，并将该函数加入当前路径。
   • 判断溢出：在每次累加栈空间后，检查当前栈消耗是否超出系统配置的最大栈空间。如果超出了限制，标记为栈溢出，并记录导致溢出的调用路径和栈使用量。此时可以立即停止该条路径的进一步递归，因为后续不会再有更优解。
   • 路径终止：如果当前函数没有更多子函数调用（即到达叶子节点），我们需要检查当前路径是否是栈空间消耗最大的路径。如果是，则更新最大栈消耗和对应的路径。
   • 回溯：递归返回时，要从当前路径中移除已经访问的节点（函数），继续搜索其他路径。

4. 判断和输出：

   • 发生溢出的情况：一旦检测到栈溢出，记录发生溢出的路径和栈消耗。根据题目要求，只输出第一次栈溢出的情况，不再继续其他路径的探索。
   • 没有发生溢出的情况：如果整个搜索结束后没有栈溢出，那么返回整个图中消耗栈空间最多的路径及其消耗量。

5. 时间和空间复杂度：

   • 时间复杂度：由于需要遍历整个调用图的所有路径，时间复杂度大致为 $O(N + M)$，其中 $N$ 是函数数量，$M$ 是调用关系数量。
   • 空间复杂度：除了输入数据占用的空间外，还需要存储当前路径（长度最多为 $N$），因此空间复杂度为 $O(N + M)$。

Python

# 读取函数个数 N
N = int(input())

# 初始化一个字典 space_map，用于存储每个函数的栈空间大小
space_map = {}

# 遍历输入 N 次，获取每个函数的名称和对应的栈空间
for i in range(N):
    fun_name , space = input().split()  # 读取函数名称和栈空间
    space_map[fun_name] = int(space)    # 将栈空间转为整数并存储在字典中

# 初始化一个字典 edge，用于存储每个函数的调用关系
edge = {}

# 读取函数调用关系的数量 m
m = int(input())

# 定义 main_func 为空字符串，用于记录主函数名称
main_func = ''

# 遍历输入 m 次，获取函数调用关系
for _ in range(m):
    line = input().split()  # 读取一行调用关系
    if main_func == '':      # 如果 main_func 为空，则将第一个函数作为主函数
        main_func = line[0]
    root = line[0]           # 调用方函数
    sons = line[1:]          # 被调用的函数列表
    edge[root] = sons        # 存储调用关系，key 为调用方，value 为被调用函数列表

# 读取系统的栈空间限制
space_limit = int(input())

# 初始化用于记录栈溢出的路径、溢出时的栈空间、最大消耗栈空间和最大路径
stop_path = []    # 记录发生栈溢出的路径
stop_space = 0    # 记录发生栈溢出时的栈空间
max_space = 0     # 记录最大栈消耗
max_path = []     # 记录最大消耗栈空间的路径
cur_path = []     # 记录当前递归中的路径

# 定义一个深度优先搜索 (DFS) 函数
def dfs(node, cur_space):
    global space_limit, stop_path, stop_space, max_space, max_path, cur_path
    cur_path.append(node)  # 当前函数加入路径

    # 如果当前路径的栈空间已经超过系统限制，记录溢出路径和栈空间
    if cur_space > space_limit:
        stop_path = cur_path.copy()  # 复制当前路径为溢出路径
        stop_space = cur_space       # 记录溢出的栈空间
        return True  # 返回 True 表示栈溢出

    # 如果当前函数没有子函数调用，即为叶子节点
    if node not in edge:
        # 如果当前路径的栈消耗大于目前记录的最大栈空间，更新最大栈空间和路径
        if cur_space > max_space:
            max_path = cur_path.copy()  # 复制当前路径为最大栈路径
            max_space = cur_space       # 更新最大栈消耗
        cur_path.pop()  # 回溯，移除当前函数
        return False    # 返回 False 表示没有栈溢出

    # 遍历当前函数的所有被调用函数（子节点）
    for son in edge[node]:
        stop_flag = dfs(son, cur_space + space_map[son])  # 递归调用下一个函数，并累加栈空间
        if stop_flag:  # 如果下层递归返回 True，表示发生栈溢出，停止递归
            return True
    cur_path.pop()  # 如果没有栈溢出，回溯，移除当前函数

# 从主函数开始进行深度优先搜索，初始栈空间为主函数的栈空间
dfs(main_func, space_map[main_func])

# 定义输出结果的变量
flag = ""         # 记录是否栈溢出
path_str = ""     # 记录路径的字符串形式
final_space = 0   # 记录最终的栈消耗

# 如果 stop_space 为 0，表示没有栈溢出
if stop_space == 0:
    flag = "false"                        # 设置 flag 为 false，表示没有栈溢出
    path_str = "-".join(max_path)         # 路径字符串为最大栈消耗路径
    final_space = max_space               # 栈消耗为最大栈空间
else:
    flag = "true"                         # 设置 flag 为 true，表示发生了栈溢出
    path_str = "-".join(stop_path)        # 路径字符串为栈溢出的路径
    final_space = stop_space              # 栈消耗为溢出的栈空间

# 输出结果，格式为：是否栈溢出 路径 栈消耗
print(flag, path_str, final_space)

java

import java.util.*;

public class StackOverflowDetection {
    // 用于存储每个函数的栈空间大小
    static Map<String, Integer> spaceMap = new HashMap<>();
    // 用于存储每个函数的调用关系
    static Map<String, List<String>> edge = new HashMap<>();
    static String mainFunc = "";
    static List<String> stopPath = new ArrayList<>();
    static int stopSpace = 0;
    static int maxSpace = 0;
    static List<String> maxPath = new ArrayList<>();
    static List<String> curPath = new ArrayList<>();
    static int spaceLimit;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取函数个数 N
        int N = Integer.parseInt(scanner.nextLine());

        // 初始化栈空间
        for (int i = 0; i < N; i++) {
            String[] input = scanner.nextLine().split(" ");
            String funName = input[0];
            int space = Integer.parseInt(input[1]);
            spaceMap.put(funName, space);
        }

        // 读取函数调用关系的数量 m
        int m = Integer.parseInt(scanner.nextLine());

        // 读取函数调用关系
        for (int i = 0; i < m; i++) {
            String[] line = scanner.nextLine().split(" ");
            if (mainFunc.isEmpty()) {
                mainFunc = line[0];
            }
            String root = line[0];
            List<String> sons = Arrays.asList(Arrays.copyOfRange(line, 1, line.length));
            edge.put(root, sons);
        }

        // 读取系统的栈空间限制
        spaceLimit = Integer.parseInt(scanner.nextLine());

        // 从主函数开始进行深度优先搜索
        dfs(mainFunc, spaceMap.get(mainFunc));

        // 输出结果
        String flag;
        String pathStr;
        int finalSpace;

        if (stopSpace == 0) {
            flag = "false";
            pathStr = String.join("-", maxPath);
            finalSpace = maxSpace;
        } else {
            flag = "true";
            pathStr = String.join("-", stopPath);
            finalSpace = stopSpace;
        }

        // 输出结果
        System.out.println(flag + " " + pathStr + " " + finalSpace);
    }

    // 定义深度优先搜索 (DFS) 函数
    static boolean dfs(String node, int curSpace) {
        curPath.add(node); // 当前函数加入路径

        // 如果当前路径的栈空间超过系统限制，记录溢出路径和栈空间
        if (curSpace > spaceLimit) {
            stopPath = new ArrayList<>(curPath); // 复制当前路径为溢出路径
            stopSpace = curSpace; // 记录溢出的栈空间
            return true; // 返回 true 表示栈溢出
        }

        // 如果当前函数没有子函数调用，即为叶子节点
        if (!edge.containsKey(node)) {
            if (curSpace > maxSpace) {
                maxPath = new ArrayList<>(curPath); // 复制当前路径为最大栈路径
                maxSpace = curSpace; // 更新最大栈消耗
            }
            curPath.remove(curPath.size() - 1); // 回溯，移除当前函数
            return false; // 返回 false 表示没有栈溢出
        }

        // 遍历当前函数的所有被调用函数（子节点）
        for (String son : edge.get(node)) {
            boolean stopFlag = dfs(son, curSpace + spaceMap.get(son)); // 递归调用下一个函数，并累加栈空间
            if (stopFlag) { // 如果下层递归返回 true，表示发生栈溢出，停止递归
                return true;
            }
        }
        curPath.remove(curPath.size() - 1); // 如果没有栈溢出，回溯，移除当前函数
        return false;
    }
}