题目链接
题目描述
在一个有向图中，每个节点有一定权值（宝石价值）。可以从任意节点出发，沿有向边行走，可以重复经过节点和边，但每个节点的权值只能被计算一次。目标是找到一条路径，使得路径上所有不同节点的权值之和最大。
解题思路
这个问题的核心在于处理“可以重复经过节点”这一条件。如果图中的一些节点可以相互到达，那么只要我们进入了这个区域，就可以访问该区域内的所有节点，从而收集全部的宝石。这个“可以相互到达的”区域，在图论中被称为强连通分量 (Strongly Connected Component, SCC)。
因此，我们可以将问题分解为以下几个步骤：
-
缩点 (Graph Condensation)：
- 使用 Tarjan 算法或者 Kosaraju 算法找到原图中的所有强连通分量。
- 将每个 SCC 视为一个“超级节点”。这个超级节点的权值等于其内部所有原始节点（房间）的宝石价值之和。
- 经过缩点后，原图会变成一个有向无环图 (Directed Acyclic Graph, DAG)。如果原图中的边
(u, v)连接了两个不同的 SCC（u属于SCC_i，v属于SCC_j），那么就在新 DAG 中添加一条从SCC_i到SCC_j的有向边。
-
DAG 上的最长路径：
- 现在问题转化为了在构造出的 DAG 上，寻找一条路径，使得路径上所有超级节点的权值之和最大。这是一个经典的动态规划问题。
- 我们定义
dp[i]为以超级节点i结尾的路径所能获得的最大宝石价值。 - 状态转移方程为：
dp[i] = scc_weight[i] + max({dp[j]})，其中j是所有能够直接到达i的超级节点。如果没有节点能到达i，则dp[i] = scc_weight[i]。 - 为了计算
dp数组，我们可以使用记忆化搜索 (DFS + memoization) 或者拓扑排序。
-
最终答案：
- 由于路径可以从任何地方开始和结束，最终的答案就是所有
dp[i]中的最大值。
- 由于路径可以从任何地方开始和结束，最终的答案就是所有
整个算法的流程是：Tarjan 找 SCC -> 缩点构建 DAG -> 在 DAG 上进行动态规划求最长链。
代码
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN], dag_adj[MAXN];
long long values[MAXN];
int n, m;
// 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];
long long dp[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);
}
}
long long dfs_dp(int u) {
if (dp[u] > 0) {
return dp[u];
}
long long max_prev_path = 0;
for (int v : dag_adj[u]) {
max_prev_path = max(max_prev_path, dfs_dp(v));
}
return dp[u] = scc_values[u] + max_prev_path;
}
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);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i);
}
}
// Build DAG
for (int u = 1; u <= n; ++u) {
for (int v : adj[u]) {
if (scc_id[u] != scc_id[v]) {
// To compute DP from predecessors, it's easier to build a reversed graph
// or compute longest path starting from a node.
// Let's compute longest path starting from a node instead.
// The edge is from scc_id[u] -> scc_id[v].
dag_adj[scc_id[u]].push_back(scc_id[v]);
}
}
}
// DP on DAG to find the longest path
// dp[u] will now store the max value of a path STARTING at scc u
long long max_total_value = 0;
for (int i = 1; i <= scc_count; ++i) {
max_total_value = max(max_total_value, dfs_dp(i));
}
cout << max_total_value << 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;
// For Tarjan's SCC
static int[] dfn, low, sccId;
static boolean[] inStack;
static Stack<Integer> st;
static int timer, sccCount;
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);
}
}
static long dfsDp(int u) {
if (dp[u] > 0) {
return dp[u];
}
long maxSuffixPath = 0;
for (int v : dagAdj.get(u)) {
maxSuffixPath = Math.max(maxSuffixPath, dfsDp(v));
}
return dp[u] = sccValues[u] + maxSuffixPath;
}
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());
adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
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());
}
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);
}
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);
}
dagAdj = new ArrayList<>();
// Use HashSet to avoid duplicate edges in DAG
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]);
}
}
}
}
dp = new long[sccCount + 1];
long maxTotalValue = 0;
for (int i = 1; i <= sccCount; i++) {
maxTotalValue = Math.max(maxTotalValue, dfsDp(i));
}
PrintWriter out = new PrintWriter(System.out);
out.println(maxTotalValue);
out.flush();
}
}
import sys
# Increase recursion limit for deep graphs in Tarjan's algorithm
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)
# For Tarjan's SCC
dfn = [0] * (n + 1)
low = [0] * (n + 1)
scc_id = [0] * (n + 1)
in_stack = [False] * (n + 1)
stack = []
timer = 0
scc_count = 0
# For DAG DP
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)
# Build DAG
dag_adj = [set() for _ in range(scc_count + 1)]
for u in range(1, n + 1):
for v in adj[u]:
if scc_id[u] != scc_id[v]:
dag_adj[scc_id[u]].add(scc_id[v])
# DP on DAG
dp = [0] * (scc_count + 1)
memo = {}
def dfs_dp(u):
if u in memo:
return memo[u]
max_suffix_path = 0
for v in dag_adj[u]:
max_suffix_path = max(max_suffix_path, dfs_dp(v))
memo[u] = scc_values[u] + max_suffix_path
return memo[u]
max_total_value = 0
for i in range(1, scc_count + 1):
max_total_value = max(max_total_value, dfs_dp(i))
print(max_total_value)
solve()
算法及复杂度
- 算法：Tarjan 算法缩点 + DAG 动态规划
- 时间复杂度：
，其中
是房间数，
是通道数。
- Tarjan 算法的时间复杂度为
- 缩点构建 DAG 的时间复杂度为
- 在 DAG 上进行记忆化搜索的复杂度为
- Tarjan 算法的时间复杂度为
- 空间复杂度：
京公网安备 11010502036488号