题解 | #星际数据下载#

题目链接

题目描述

在一个有向图中，每个节点有权值（数据量）。从一个指定的起点 S 出发，沿着有向边行走，可以重复经过节点和边，但每个节点的权值只能收集一次。当到达任意一个指定的终点时，任务结束。目标是找到一条从起点到任意终点的路径，使得路径上所有不同节点的权值之和最大。

解题思路

本题是上一题“魔法迷宫探宝”的变种。核心思想依然是强连通分量 (SCC) 缩点，因为一旦进入一个 SCC，就可以访问该 SCC 内的所有节点。主要区别在于本题有固定的起点和一组终点。

算法步骤如下：

SCC 缩点：
- 使用 Tarjan 算法找到原图中的所有强连通分量。
- 将每个 SCC 视为一个“超级节点”，其权值为该 SCC 内部所有原始空间站的数据量之和。
- 根据原图的边构建一个有向无环图 (DAG)，其中节点是 SCC。
确定起点和终点 SCC：
- 找到原始起点 S 所在的 SCC，记为 start_scc。
- 标记所有包含至少一个原始数据中转站的 SCC，这些是终点 SCC 集合 terminal_sccs。
DAG 上的动态规划：
- 问题转化为在 DAG 中寻找从 start_scc 到 terminal_sccs 中任意一个节点的最长路径。
- 我们可以使用拓扑排序来处理 DAG 上的动态规划。
- 定义 dp[i] 为从 start_scc 出发到达 SCC i 的路径所能收集的最大数据总量。
- 初始化：dp 数组所有元素初始化为 0。dp[start_scc] 初始化为 start_scc 的权值。
- 状态转移：
  1. 对 DAG 进行拓扑排序。
  2. 按拓扑序遍历所有 SCC。对于当前 SCC u，如果它能从 start_scc 到达（即 dp[u] > 0），则用 dp[u] 更新其所有后继 SCC v 的 dp 值：dp[v] = max(dp[v], dp[u] + scc_value[v])。
最终答案：
- DP 过程结束后，遍历所有终点 SCC，在它们对应的 dp 值中取最大值，即为最终答案。

整个算法的流程是：Tarjan 找 SCC -> 缩点构建 DAG -> 拓扑排序 + DP 求最长链 -> 在终点中找最大值。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>

using namespace std;

const int MAXN = 200005;
vector<int> adj[MAXN], dag_adj[MAXN];
long long values[MAXN];
int n, m, start_node, p;

// For Tarjan's SCC
int dfn[MAXN], low[MAXN], scc_id[MAXN];
bool in_stack[MAXN];
stack<int> st;
int timer, scc_count;

// For DAG DP
long long scc_values[MAXN];
int dag_in_degree[MAXN];
long long dp[MAXN];
bool is_terminal_scc[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    in_stack[u] = true;

    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_count++;
        int node;
        do {
            node = st.top();
            st.pop();
            in_stack[node] = false;
            scc_id[node] = scc_count;
            scc_values[scc_count] += values[node];
        } while (node != u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> values[i];
    }

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

    cin >> start_node >> p;
    vector<int> terminals(p);
    for (int i = 0; i < p; ++i) {
        cin >> terminals[i];
    }

    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // Mark terminal SCCs
    for (int terminal_node : terminals) {
        is_terminal_scc[scc_id[terminal_node]] = true;
    }

    // Build DAG and calculate in-degrees
    for (int u = 1; u <= n; ++u) {
        for (int v : adj[u]) {
            if (scc_id[u] != scc_id[v]) {
                dag_adj[scc_id[u]].push_back(scc_id[v]);
                dag_in_degree[scc_id[v]]++;
            }
        }
    }

    // DP on DAG using topological sort
    queue<int> q;
    for (int i = 1; i <= scc_count; ++i) {
        if (dag_in_degree[i] == 0) {
            q.push(i);
        }
    }
    
    int start_scc = scc_id[start_node];
    dp[start_scc] = scc_values[start_scc];
    
    // We need to process nodes in topological order
    vector<int> topo_order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        for (int v : dag_adj[u]) {
            dag_in_degree[v]--;
            if (dag_in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    for (int u : topo_order) {
        // if dp[u] is 0 and u is not start_scc, it means it's unreachable
        if (dp[u] == 0 && u != start_scc) continue;

        for (int v : dag_adj[u]) {
            dp[v] = max(dp[v], dp[u] + scc_values[v]);
        }
    }

    long long max_data = 0;
    for (int i = 1; i <= scc_count; ++i) {
        if (is_terminal_scc[i]) {
            max_data = max(max_data, dp[i]);
        }
    }

    cout << max_data << endl;

    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static List<List<Integer>> adj, dagAdj;
    static long[] values, sccValues, dp;
    static int n, m, startNode, p;

    // For Tarjan's SCC
    static int[] dfn, low, sccId;
    static boolean[] inStack;
    static Stack<Integer> st;
    static int timer, sccCount;

    // For DAG DP
    static int[] dagInDegree;
    static boolean[] isTerminalScc;

    static void tarjan(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        inStack[u] = true;

        for (int v : adj.get(u)) {
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            sccCount++;
            int node;
            do {
                node = st.pop();
                inStack[node] = false;
                sccId[node] = sccCount;
                sccValues[sccCount] += values[node];
            } while (node != u);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st_in = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st_in.nextToken());
        m = Integer.parseInt(st_in.nextToken());

        values = new long[n + 1];
        st_in = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            values[i] = Long.parseLong(st_in.nextToken());
        }

        adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            st_in = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st_in.nextToken());
            int v = Integer.parseInt(st_in.nextToken());
            adj.get(u).add(v);
        }

        st_in = new StringTokenizer(br.readLine());
        startNode = Integer.parseInt(st_in.nextToken());
        p = Integer.parseInt(st_in.nextToken());

        int[] terminals = new int[p];
        st_in = new StringTokenizer(br.readLine());
        for (int i = 0; i < p; i++) {
            terminals[i] = Integer.parseInt(st_in.nextToken());
        }

        dfn = new int[n + 1]; low = new int[n + 1]; sccId = new int[n + 1];
        inStack = new boolean[n + 1]; st = new Stack<>();
        sccValues = new long[n + 1]; timer = 0; sccCount = 0;
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == 0) tarjan(i);
        }
        
        isTerminalScc = new boolean[sccCount + 1];
        for (int terminal : terminals) {
            isTerminalScc[sccId[terminal]] = true;
        }

        dagAdj = new ArrayList<>();
        dagInDegree = new int[sccCount + 1];
        Set<Integer>[] dagAdjSet = new HashSet[sccCount + 1];
        for (int i = 0; i <= sccCount; i++) {
            dagAdj.add(new ArrayList<>());
            dagAdjSet[i] = new HashSet<>();
        }

        for (int u = 1; u <= n; u++) {
            for (int v : adj.get(u)) {
                if (sccId[u] != sccId[v]) {
                    if (dagAdjSet[sccId[u]].add(sccId[v])) {
                        dagAdj.get(sccId[u]).add(sccId[v]);
                        dagInDegree[sccId[v]]++;
                    }
                }
            }
        }
        
        Queue<Integer> q = new LinkedList<>();
        List<Integer> topoOrder = new ArrayList<>();
        for (int i = 1; i <= sccCount; i++) {
            if (dagInDegree[i] == 0) q.add(i);
        }

        while (!q.isEmpty()) {
            int u = q.poll();
            topoOrder.add(u);
            for (int v : dagAdj.get(u)) {
                dagInDegree[v]--;
                if (dagInDegree[v] == 0) q.add(v);
            }
        }
        
        dp = new long[sccCount + 1];
        int startScc = sccId[startNode];
        dp[startScc] = sccValues[startScc];

        for (int u : topoOrder) {
            if (dp[u] == 0 && u != startScc) continue;
            for (int v : dagAdj.get(u)) {
                dp[v] = Math.max(dp[v], dp[u] + sccValues[v]);
            }
        }

        long maxData = 0;
        for (int i = 1; i <= sccCount; i++) {
            if (isTerminalScc[i]) {
                maxData = Math.max(maxData, dp[i]);
            }
        }

        PrintWriter out = new PrintWriter(System.out);
        out.println(maxData);
        out.flush();
    }
}

import sys
from collections import deque

# Increase recursion limit for deep graphs
sys.setrecursionlimit(200005)

def solve():
    try:
        n_str, m_str = sys.stdin.readline().split()
        n, m = int(n_str), int(m_str)
        values_str = sys.stdin.readline().split()
        values = [0] + [int(v) for v in values_str]
    except (IOError, ValueError):
        return

    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)

    start_node, p = map(int, sys.stdin.readline().split())
    terminals = list(map(int, sys.stdin.readline().split()))

    # --- Tarjan's Algorithm ---
    dfn = [0] * (n + 1); low = [0] * (n + 1); scc_id = [0] * (n + 1)
    in_stack = [False] * (n + 1); stack = []
    timer = 0; scc_count = 0
    scc_values = [0] * (n + 1)

    def tarjan(u):
        nonlocal timer, scc_count
        timer += 1
        dfn[u] = low[u] = timer
        stack.append(u)
        in_stack[u] = True

        for v in adj[u]:
            if dfn[v] == 0:
                tarjan(v)
                low[u] = min(low[u], low[v])
            elif in_stack[v]:
                low[u] = min(low[u], dfn[v])
        
        if dfn[u] == low[u]:
            scc_count += 1
            while True:
                node = stack.pop()
                in_stack[node] = False
                scc_id[node] = scc_count
                scc_values[scc_count] += values[node]
                if node == u:
                    break
    
    for i in range(1, n + 1):
        if dfn[i] == 0:
            tarjan(i)
    
    # --- DP on DAG ---
    is_terminal_scc = [False] * (scc_count + 1)
    for t_node in terminals:
        is_terminal_scc[scc_id[t_node]] = True

    dag_adj = [set() for _ in range(scc_count + 1)]
    dag_in_degree = [0] * (scc_count + 1)
    for u in range(1, n + 1):
        for v in adj[u]:
            if scc_id[u] != scc_id[v]:
                if scc_id[v] not in dag_adj[scc_id[u]]:
                    dag_adj[scc_id[u]].add(scc_id[v])
                    dag_in_degree[scc_id[v]] += 1
    
    # Topological sort
    q = deque([i for i in range(1, scc_count + 1) if dag_in_degree[i] == 0])
    topo_order = []
    while q:
        u = q.popleft()
        topo_order.append(u)
        for v in dag_adj[u]:
            dag_in_degree[v] -= 1
            if dag_in_degree[v] == 0:
                q.append(v)
    
    # DP
    dp = [0] * (scc_count + 1)
    start_scc = scc_id[start_node]
    dp[start_scc] = scc_values[start_scc]
    
    for u in topo_order:
        if dp[u] == 0 and u != start_scc:
            continue
        for v in dag_adj[u]:
            dp[v] = max(dp[v], dp[u] + scc_values[v])

    max_data = 0
    for i in range(1, scc_count + 1):
        if is_terminal_scc[i]:
            max_data = max(max_data, dp[i])
    
    print(max_data)

solve()

算法及复杂度

算法：Tarjan 算法缩点 + 拓扑排序 + DAG 动态规划
时间复杂度： $O(N+M)$ ，其中 $N$ 是空间站数量， $M$ 是通道数量。
- Tarjan 算法： $O(N+M)$ 。
- 缩点构建 DAG 及计算入度： $O(N+M)$ 。
- 拓扑排序： $O(N+M)$ 。
- DAG 上的 DP： $O(N+M)$ 。
空间复杂度： $O(N+M)$ ，用于存储图、辅助数组等。