解题思路

1. 建图与输入

   • 每一行 a b size 表示：函数 a 调用函数 b，这次调用需要 size 字节的栈内存。
   • 这就是一张 有向图，边权为栈大小。
   • 函数编号范围为 0~999，总边数 ≤ 1000。

2. 检测递归（有向环）

   • 题目说如果存在递归（函数调用有环），直接输出 -1。

   • 对有向图做 拓扑排序（Kahn 算法）：

     • 统计所有点入度，把入度为 0 的点入队。
     • 不断出队、删边、更新入度并加入新的入度为 0 的点。
     • 最后如果被弹出的点数 < 图中实际点数，则说明图中存在有向环。

   • 一旦有环，立刻输出 -1，结束。

3. 在 DAG 中求最大栈大小与相应最长调用链

   • 图无环后，是一张 DAG。

   • 定义状态（以某个函数为“调用链最后一个函数”）：

     • dpSum[u]：以 u 结尾的调用链的最大栈内存和（即边权之和）。
     • dpLen[u]：在上述最大栈内存方案下，调用链中函数个数（节点数）。

   • 初始化：

     • 对于出现过的每个函数 u，先认为它单独一个函数：dpSum[u] = 0，dpLen[u] = 1。

   • 按拓扑序遍历所有点 u，对每条边 u -> v，边权为 w：

     • 候选链：从 u 的最佳链再调用 v：

       • candSum = dpSum[u] + w
       • candLen = dpLen[u] + 1

     • 用字典序比较更新 v：

       • 如果 candSum > dpSum[v]，更新；
       • 如果 candSum == dpSum[v] 且 candLen > dpLen[v]，也更新（同样栈大小时要更长的函数个数）。

   • 遍历所有出现过的点，取：

     • 最大的 dpSum 作为系统运行时需要开辟的最大栈大小；
     • 在该最大栈大小下对应的最大 dpLen 作为调用链上的函数个数。

4. 输出

   • 若存在环，输出：-1
   • 否则输出：最大栈大小 最大调用链函数个数，中间空格分隔。

核心算法：

• 拓扑排序检测有向环；
• 在 DAG 上的最长路径（带权 + 次要关键字为路径长度）DP。

复杂度分析

• 设函数点数为 V（最多 1000），调用关系数为 E（最多 1000）。

• 拓扑排序：时间复杂度 O(V + E)，空间复杂度 O(V + E)。

• DAG 上 DP：同样 O(V + E) 时间、O(V) 额外空间。

• 总体：

  • 时间复杂度：O(V + E)，在数据范围内非常充足。
  • 空间复杂度：O(V + E)。

代码实现

Python

import sys
from collections import deque

# 计算最大栈大小和最长调用链长度的函数
def solve():
    data = sys.stdin.read().split()
    if not data:
        return
    m = int(data[0])  # 调用关系条数

    MAX_ID = 1000  # 函数 id 范围 0~999
    adj = [[] for _ in range(MAX_ID)]  # 邻接表：adj[u] = [(v, w), ...]
    indeg = [0] * MAX_ID              # 入度
    exist = [False] * MAX_ID          # 该函数是否出现过

    idx = 1
    for _ in range(m):
        u = int(data[idx]); v = int(data[idx + 1]); w = int(data[idx + 2])
        idx += 3
        adj[u].append((v, w))
        indeg[v] += 1
        exist[u] = True
        exist[v] = True

    # 统计真正存在的函数个数
    node_count = sum(1 for x in exist if x)

    # 拓扑排序（Kahn），同时检测是否有环
    q = deque()
    for i in range(MAX_ID):
        if exist[i] and indeg[i] == 0:
            q.append(i)

    topo = []
    while q:
        u = q.popleft()
        topo.append(u)
        for v, w in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and exist[v]:
                q.append(v)

    if len(topo) != node_count:
        # 图中存在有向环 => 递归
        print(-1)
        return

    # DAG 上 DP 求最长路径（以栈大小为主关键字，长度为次关键字）
    dpSum = [0] * MAX_ID  # 最大栈大小
    dpLen = [0] * MAX_ID  # 在该栈大小下的最大函数个数
    for i in range(MAX_ID):
        if exist[i]:
            dpLen[i] = 1  # 单独一个函数

    for u in topo:
        for v, w in adj[u]:
            candSum = dpSum[u] + w
            candLen = dpLen[u] + 1
            if candSum > dpSum[v] or (candSum == dpSum[v] and candLen > dpLen[v]):
                dpSum[v] = candSum
                dpLen[v] = candLen

    # 找到整体最优答案
    bestSum = 0
    bestLen = 0
    for i in range(MAX_ID):
        if exist[i]:
            if dpSum[i] > bestSum or (dpSum[i] == bestSum and dpLen[i] > bestLen):
                bestSum = dpSum[i]
                bestLen = dpLen[i]

    print(bestSum, bestLen)


if __name__ == "__main__":
    solve()

Java

import java.util.*;

// 主类名必须为 Main
public class Main {

    // 边结构，表示一条调用关系
    static class Edge {
        int to;   // 终点函数 id
        int w;    // 调用栈大小
        Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }

    // 计算并输出结果的函数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) {
            return;
        }
        int m = sc.nextInt();  // 调用关系条数

        final int MAX_ID = 1000;  // 函数 id 范围 0~999
        
        ArrayList<Edge>[] g = new ArrayList[MAX_ID];
        for (int i = 0; i < MAX_ID; i++) {
            g[i] = new ArrayList<>();
        }

        int[] indeg = new int[MAX_ID];   // 入度
        boolean[] exist = new boolean[MAX_ID];  // 该函数是否出现过

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            g[u].add(new Edge(v, w));
            indeg[v]++;
            exist[u] = true;
            exist[v] = true;
        }

        // 统计真正存在的函数个数
        int nodeCount = 0;
        for (int i = 0; i < MAX_ID; i++) {
            if (exist[i]) nodeCount++;
        }

        // 拓扑排序（Kahn 算法）
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < MAX_ID; i++) {
            if (exist[i] && indeg[i] == 0) {
                q.offer(i);
            }
        }

        int[] topo = new int[nodeCount]; // 存拓扑序
        int idx = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            topo[idx++] = u;
            for (Edge e : g[u]) {
                int v = e.to;
                indeg[v]--;
                if (indeg[v] == 0 && exist[v]) {
                    q.offer(v);
                }
            }
        }

        if (idx != nodeCount) {
            // 有向图中存在环 => 递归
            System.out.println(-1);
            return;
        }

        // DAG 上 DP
        int[] dpSum = new int[MAX_ID];  // 最大栈大小
        int[] dpLen = new int[MAX_ID];  // 最大函数个数
        for (int i = 0; i < MAX_ID; i++) {
            if (exist[i]) {
                dpLen[i] = 1; // 单独一个函数
            }
        }

        for (int i = 0; i < nodeCount; i++) {
            int u = topo[i];
            for (Edge e : g[u]) {
                int v = e.to;
                int w = e.w;
                int candSum = dpSum[u] + w;
                int candLen = dpLen[u] + 1;
                if (candSum > dpSum[v] || (candSum == dpSum[v] && candLen > dpLen[v])) {
                    dpSum[v] = candSum;
                    dpLen[v] = candLen;
                }
            }
        }

        int bestSum = 0;
        int bestLen = 0;
        for (int i = 0; i < MAX_ID; i++) {
            if (!exist[i]) continue;
            if (dpSum[i] > bestSum || (dpSum[i] == bestSum && dpLen[i] > bestLen)) {
                bestSum = dpSum[i];
                bestLen = dpLen[i];
            }
        }

        System.out.println(bestSum + " " + bestLen);
    }
}

C++

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

// 计算最大栈大小和最长调用链长度的函数
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    if (!(cin >> m)) {
        return 0;
    }

    const int MAX_ID = 1000; // 函数 id 范围 0~999
    vector<pair<int, int>> adj[MAX_ID]; // 邻接表：{终点, 栈大小}
    int indeg[MAX_ID] = {0};            // 入度
    bool exist[MAX_ID] = {false};       // 该函数是否出现过

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        indeg[v]++;
        exist[u] = exist[v] = true;
    }

    // 统计真正存在的函数个数
    int nodeCount = 0;
    for (int i = 0; i < MAX_ID; ++i) {
        if (exist[i]) nodeCount++;
    }

    // 拓扑排序（Kahn 算法）
    queue<int> q;
    for (int i = 0; i < MAX_ID; ++i) {
        if (exist[i] && indeg[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topo;
    topo.reserve(nodeCount);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);
        for (auto &e : adj[u]) {
            int v = e.first;
            indeg[v]--;
            if (indeg[v] == 0 && exist[v]) {
                q.push(v);
            }
        }
    }

    if ((int)topo.size() != nodeCount) {
        // 存在有向环 => 递归
        cout << -1 << "\n";
        return 0;
    }

    // DAG 上 DP
    int dpSum[MAX_ID] = {0}; // 最大栈大小
    int dpLen[MAX_ID] = {0}; // 最大函数个数
    for (int i = 0; i < MAX_ID; ++i) {
        if (exist[i]) dpLen[i] = 1; // 单独一个函数
    }

    for (int u : topo) {
        for (auto &e : adj[u]) {
            int v = e.first;
            int w = e.second;
            int candSum = dpSum[u] + w;
            int candLen = dpLen[u] + 1;
            if (candSum > dpSum[v] || (candSum == dpSum[v] && candLen > dpLen[v])) {
                dpSum[v] = candSum;
                dpLen[v] = candLen;
            }
        }
    }

    int bestSum = 0;
    int bestLen = 0;
    for (int i = 0; i < MAX_ID; ++i) {
        if (!exist[i]) continue;
        if (dpSum[i] > bestSum || (dpSum[i] == bestSum && dpLen[i] > bestLen)) {
            bestSum = dpSum[i];
            bestLen = dpLen[i];
        }
    }

    cout << bestSum << " " << bestLen << "\n";
    return 0;
}

题目内容

给定一系列函数调用关系和调用所需开辟的栈内存大小，输出

1.系统运行时所需开辟的最大栈大小(栈空间是函数调用链上所需栈内存的总和)

2.满足开辟栈内存最大时，调用链长度的最大长度(有多个调用关系时输出最长调用链上的函数个数值)

输入描述

输入函数的调用关系和所需开辟的栈大小，输入第一行为调用关系数目从第二行开始为调用关系每行一个;

例如: $2$ $0$ $1$ $128$ $1$ $2$ $128$

表示有两个调用关系:函数 $0$ 调用函数 $1$ ，开辟 $128$ 字节栈，函数 $1$ 调用函数 $2$ ，开辟 $128$ 字节栈

调用关系可如下图表示:

约束:

1.函数的 $id$ 取值范围为 $0<= id <=999$

2.栈大小的范围为 $8<= size<=10240$

3.调用关系的总个数 $<= 1000$

输出描述

1.如果出现递归(环状的调用关系)，输出 $-1$

2.如果找到分配的最大栈的调用关系时，输出两个值，第一个值表示最大分配的栈内存的值，第二个值表示满足栈内存最大时，调用链的最大长度，使用空格分割

样例1

输入

3
0 1 128
1 2 128
2 0 128

输出

-1

说明

输入的函数调用关系中存在递归，输出 $-1$

样例2

输入

3
0 1 128
1 2 128
1 3 32

输出

256 3

说明

$0$ $1$ $2$ 的调用关系会开辟 $256$ 字节栈内存

$0$ $1$ $3$ 的调用关系会开辟 $160$ 字节栈内存

$0$ $1$ $2$ 的调用关系开辟的栈内存最大，调用关系长度最长为 $3$，所以输出: $256$ $3$