题目链接
题目描述
在一张带点权的无向图中，寻找一条从顶点1到顶点N的简单路径，要求路径上节点的权值是广义单调递增（非递减）的。在所有满足条件的路径中，找出一条路径，使其包含的不同权值数量最多。输出这个最多的数量。如果不存在这样的路径，则得分为0。
解题思路
这是一个在图上寻找满足特定条件的、从固定起点到固定终点的最长路径问题，可以利用动态规划来解决。关键在于“权值非递减”和“1->N”这两个约束。
DP on DAG
-
模型转换： “路径上节点权值非递减”的限制，意味着我们只能从一个节点
u移动到其邻居v当且仅当weight[u] <= weight[v]。这个限制将原始的无向图隐式地转换为了一个有向无环图 (DAG)。我们的目标是在这个 DAG 上寻找一条特殊的“最长路径”，其中路径的长度定义为路径上不同权值的数量。 -
DP 状态定义： 我们定义
dp[u]为：所有从顶点1出发、以顶点u结尾的、满足权值非递减条件的路径中，能取得的最大得分（即不同权值的最大数量）。 最终的答案就是dp[N]。 -
初始化： 由于路径必须从顶点1开始，我们将
dp[1]初始化为1（代表路径只包含起点自身），而所有其他dp[i](i > 1) 初始化为0，表示尚未从顶点1通过合法路径到达。 -
计算顺序： 为了正确地进行状态转移，在计算
dp[u]时，我们必须保证所有能够转移到u的前驱节点v（即weight[v] <= weight[u]）的dp值都已经被计算完毕。因此，我们必须按照节点的权值从小到大的顺序来处理节点。 -
状态转移与同权值处理：
算法流程与之前类似，但现在加入了对路径是否从1开始的判断 (
dp[v] > 0)：a. 按权值分组并从小到大排序。
b. 遍历每个权值
w：i. 跨权值更新：对于权值为
w的节点u，遍历其邻居v。如果weight[v] < w且dp[v] > 0（表示存在一条从1到v的合法路径），则用dp[v] + 1更新dp[u]。ii. 同权值传播：在权值为
w的节点构成的子图上传播分数。对于该子图的每个连通分量，如果分量中至少有一个节点v拥有dp[v] > 0的值，则该分量内所有节点的dp值都应更新为分量中dp值的最大值。 -
最终结果： 所有节点处理完毕后，
dp[N]的值即为最终答案。如果dp[N]仍为0，说明没有从1到N的非递减路径。
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<int> w(n + 1);
map<int, vector<int>> nodes_by_weight;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
nodes_by_weight[w[i]].push_back(i);
}
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> dp(n + 1, 0);
if (n > 0) {
dp[1] = 1;
}
vector<int> sorted_unique_weights;
for (auto const& [weight, nodes] : nodes_by_weight) {
sorted_unique_weights.push_back(weight);
}
for (int weight : sorted_unique_weights) {
// Step A: Update from smaller weights
for (int u : nodes_by_weight[weight]) {
for (int v : adj[u]) {
if (w[v] < w[u] && dp[v] > 0) {
dp[u] = max(dp[u], dp[v] + 1);
}
}
}
// Step B: Propagate max score within the same-weight component
vector<bool> visited(n + 1, false);
for (int u : nodes_by_weight[weight]) {
if (!visited[u] && dp[u] > 0) { // Only start traversal from reachable nodes
vector<int> component;
int max_score_in_component = 0;
queue<int> q;
q.push(u);
visited[u] = true;
while(!q.empty()){
int curr = q.front();
q.pop();
component.push_back(curr);
max_score_in_component = max(max_score_in_component, dp[curr]);
for(int neighbor : adj[curr]){
if(w[neighbor] == weight && !visited[neighbor]){
visited[neighbor] = true;
q.push(neighbor);
}
}
}
for (int node : component) {
dp[node] = max(dp[node], max_score_in_component);
}
}
}
}
cout << (n > 0 ? dp[n] : 0) << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] w = new int[n + 1];
Map<Integer, List<Integer>> nodesByWeight = new TreeMap<>();
for (int i = 1; i <= n; i++) {
w[i] = sc.nextInt();
nodesByWeight.computeIfAbsent(w[i], k -> new ArrayList<>()).add(i);
}
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
adj.get(u).add(v);
adj.get(v).add(u);
}
int[] dp = new int[n + 1];
if (n > 0) {
dp[1] = 1;
}
for (int weight : nodesByWeight.keySet()) {
List<Integer> currentWeightNodes = nodesByWeight.get(weight);
// Step A: Update from smaller weights
for (int u : currentWeightNodes) {
for (int v : adj.get(u)) {
if (w[v] < w[u] && dp[v] > 0) {
dp[u] = Math.max(dp[u], dp[v] + 1);
}
}
}
// Step B: Propagate within same-weight components
boolean[] visited = new boolean[n + 1];
for (int u : currentWeightNodes) {
if (!visited[u] && dp[u] > 0) {
List<Integer> component = new ArrayList<>();
int maxScoreInComponent = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(u);
visited[u] = true;
while (!q.isEmpty()) {
int curr = q.poll();
component.add(curr);
maxScoreInComponent = Math.max(maxScoreInComponent, dp[curr]);
for (int neighbor : adj.get(curr)) {
if (w[neighbor] == weight && !visited[neighbor]) {
visited[neighbor] = true;
q.offer(neighbor);
}
}
}
for (int node : component) {
dp[node] = Math.max(dp[node], maxScoreInComponent);
}
}
}
}
System.out.println(n > 0 ? dp[n] : 0);
}
}
import sys
from collections import defaultdict, deque
def main():
input = sys.stdin.readline
try:
n, m = map(int, input().split())
except ValueError:
print(0)
return
weights = [0] + list(map(int, input().split()))
nodes_by_weight = defaultdict(list)
for i in range(1, n + 1):
nodes_by_weight[weights[i]].append(i)
adj = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
dp = [0] * (n + 1)
if n > 0:
dp[1] = 1
sorted_unique_weights = sorted(nodes_by_weight.keys())
for weight in sorted_unique_weights:
# Step A: Update from nodes with smaller weights
for u in nodes_by_weight[weight]:
for v in adj[u]:
if weights[v] < weights[u] and dp[v] > 0:
dp[u] = max(dp[u], dp[v] + 1)
# Step B: Propagate max score within same-weight components
visited = set()
for u_start in nodes_by_weight[weight]:
if u_start not in visited and dp[u_start] > 0:
component = []
max_score_in_component = 0
q = deque([u_start])
visited.add(u_start)
while q:
u = q.popleft()
component.append(u)
max_score_in_component = max(max_score_in_component, dp[u])
for v in adj[u]:
if weights[v] == weight and v not in visited:
visited.add(v)
q.append(v)
for node in component:
dp[node] = max(dp[node], max_score_in_component)
print(dp[n] if n > 0 else 0)
if __name__ == "__main__":
main()
算法及复杂度
- 算法：动态规划
- 时间复杂度：
。我们将每个节点和每条边访问常数次。首先按权值对节点分组需要
。然后遍历所有权值，对于每个权值
w，我们遍历所有权值为w的节点及其边（跨权值更新），然后再次遍历它们进行同权值传播。总体来看，每个节点和边都被处理有限次，所以总复杂度是线性的。 - 空间复杂度：
dp数组以及按权值分组的节点列表。
京公网安备 11010502036488号