题解 | #游游的旅行#

题目链接

游游的旅行

题目描述

在一个由 N 个景点和 M 条路径组成的无向图中，游游和小伙伴计划进行一次为时 T 分钟的旅行。

每个景点 i 有一个游览耗时 time[i]，并能为游游和小伙伴分别增加 joy1[i] 和 joy2[i] 的愉悦度。
每条路径连接两个景点，并有相应的通行耗时。
旅行开始时，他们会等概率地从 N 个景点中随机选择一个作为起点。
每到达一个景点，他们会先花费时间游览该景点并获得愉悦度。之后，他们会查看所有与当前景点直接相连的下一个景点，找出那些“来得及游玩”（即剩余时间足够支付路程耗时和下一个景点的游览耗时）的景点，并从这些景点中等概率随机选择一个作为下一个目的地。
如果没有“来得及游玩”的下一个景点，旅行就提前结束。

要求计算旅行结束后，游游和小伙伴各自的期望愉悦度。

解题思路

1. 问题分析：期望 DP

这是一个典型的在图上求解期望值的问题。由于旅行的过程是一个有状态、有概率转移的决策过程，我们可以使用动态规划（特别是期望 DP）来解决。

2. 状态定义

关键在于定义状态。一个状态需要包含所有影响未来决策的信息，这里是“当前所在的景点”和“剩余的时间”。

我们定义一个函数 dfs(u, t)，它返回一个二元组 {E_1, E_2}，分别表示：

E_1：当前位于景点 u，剩余总时间为 t 时，从此刻（游览 u）开始，直到旅途结束，游游能获得的期望愉悦度。
E_2：同样条件下，小伙伴能获得的期望愉悦度。

3. 状态转移方程（递推关系）

dfs(u, t) 的计算逻辑如下：

无法游览：如果 t < time[u]，说明时间不够游览当前景点 u，旅程从 u 开始的这条分支获得的愉悦度为 0。这是递归的边界条件。
可以游览：如果 t >= time[u]，则：

a. 获得当前愉悦度：首先，他们会游览景点 u，获得 joy1[u] 和 joy2[u] 的愉悦度。

b. 更新时间：游览后，剩余时间变为 t' = t - time[u]。

c. 寻找下一个目的地：找出所有与 u 相邻的景点 v，满足 t' >= travel_time(u, v) + time[v]。这些是“来得及游玩”的有效下一站。设这样的景点集合为 V_valid，其大小为 k。

d. 计算未来期望：
- 如果 k = 0，没有有效的下一站，旅程在此结束。未来的期望愉悦度为 0。
- 如果 k > 0，他们会以 1/k 的概率选择 V_valid 中的任意一个景点 v。到达 v 时，剩余时间为 t' - travel_time(u, v)。从 v 开始的期望愉悦度就是 dfs(v, t' - travel_time(u, v))。根据期望的线性性质，从 u 出发后，未来的总期望愉悦度是所有可能的下一站的期望愉悦度之和的平均值。
  
  FutureExpectation1 = (1/k) * Σ_{v ∈ V_valid} dfs(v, t - time[u] - travel_time(u,v)).E_1
  
  FutureExpectation2 = (1/k) * Σ_{v ∈ V_valid} dfs(v, t - time[u] - travel_time(u,v)).E_2
e. 总期望：dfs(u, t) 的总期望值 = 当前获得的愉悦度 + 未来的期望愉悦度。

dfs(u, t).E_1 = joy1[u] + FutureExpectation1

dfs(u, t).E_2 = joy2[u] + FutureExpectation2

4. 记忆化搜索

上述递归过程会产生大量重叠子问题（例如，通过不同路径在同一时间到达同一景点）。为了避免重复计算，我们使用一个二维数组 dp[N+1][T+1] 来存储 dfs(u, t) 的计算结果。这就是记忆化搜索。

5. 最终答案

旅程开始时，会以 1/N 的概率选择任意一个景点 s (从 1 到 N) 作为起点。因此，总的期望愉悦度是所有从 s 出发的期望愉悦度之和的平均值。

TotalExpectation1 = (1/N) * Σ_{s=1 to N} dfs(s, T).E_1

TotalExpectation2 = (1/N) * Σ_{s=1 to N} dfs(s, T).E_2

代码

c++
java
python

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

struct Spot {
    int t, y1, y2;
};

struct Edge {
    int to, time;
};

int N, M, T;
vector<Spot> spots;
vector<vector<Edge>> adj;
vector<vector<pair<double, double>>> memo;
vector<vector<bool>> visited;

pair<double, double> dfs(int u, int remaining_time) {
    if (remaining_time < spots[u].t) {
        return {0.0, 0.0};
    }
    if (visited[u][remaining_time]) {
        return memo[u][remaining_time];
    }

    int time_after_visit = remaining_time - spots[u].t;
    
    vector<int> valid_next_spots;
    for (const auto& edge : adj[u]) {
        if (time_after_visit >= edge.time + spots[edge.to].t) {
            valid_next_spots.push_back(edge.to);
        }
    }

    double future_joy1 = 0.0;
    double future_joy2 = 0.0;
    int k = valid_next_spots.size();

    if (k > 0) {
        for (int v_node : valid_next_spots) {
            int time_at_v = 0;
            // Find the edge time again
            for(const auto& edge : adj[u]){
                if(edge.to == v_node){
                    time_at_v = time_after_visit - edge.time;
                    break;
                }
            }
            pair<double, double> next_joy = dfs(v_node, time_at_v);
            future_joy1 += next_joy.first;
            future_joy2 += next_joy.second;
        }
        future_joy1 /= k;
        future_joy2 /= k;
    }

    double total_joy1 = spots[u].y1 + future_joy1;
    double total_joy2 = spots[u].y2 + future_joy2;

    visited[u][remaining_time] = true;
    memo[u][remaining_time] = {total_joy1, total_joy2};
    return {total_joy1, total_joy2};
}

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

    cin >> N >> M >> T;

    spots.resize(N + 1);
    adj.resize(N + 1);
    memo.resize(N + 1, vector<pair<double, double>>(T + 1));
    visited.resize(N + 1, vector<bool>(T + 1, false));

    for (int i = 1; i <= N; ++i) {
        cin >> spots[i].t >> spots[i].y1 >> spots[i].y2;
    }

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

    double total_expected_joy1 = 0.0;
    double total_expected_joy2 = 0.0;

    for (int i = 1; i <= N; ++i) {
        pair<double, double> result = dfs(i, T);
        total_expected_joy1 += result.first;
        total_expected_joy2 += result.second;
    }

    cout << fixed << setprecision(5) << total_expected_joy1 / N << " " << total_expected_joy2 / N << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static class Spot {
        int t, y1, y2;
        public Spot(int t, int y1, int y2) {
            this.t = t;
            this.y1 = y1;
            this.y2 = y2;
        }
    }

    static class Edge {
        int to, time;
        public Edge(int to, int time) {
            this.to = to;
            this.time = time;
        }
    }
    
    static class JoyPair {
        double joy1, joy2;
        public JoyPair(double joy1, double joy2) {
            this.joy1 = joy1;
            this.joy2 = joy2;
        }
    }

    static int N, M, T;
    static Spot[] spots;
    static List<Edge>[] adj;
    static JoyPair[][] memo;
    static boolean[][] visited;

    static JoyPair dfs(int u, int remainingTime) {
        if (remainingTime < spots[u].t) {
            return new JoyPair(0.0, 0.0);
        }
        if (visited[u][remainingTime]) {
            return memo[u][remainingTime];
        }

        int timeAfterVisit = remainingTime - spots[u].t;

        List<Edge> validNextEdges = new ArrayList<>();
        for (Edge edge : adj[u]) {
            if (timeAfterVisit >= edge.time + spots[edge.to].t) {
                validNextEdges.add(edge);
            }
        }

        double futureJoy1 = 0.0;
        double futureJoy2 = 0.0;
        int k = validNextEdges.size();

        if (k > 0) {
            for (Edge edge : validNextEdges) {
                int timeAtV = timeAfterVisit - edge.time;
                JoyPair nextJoy = dfs(edge.to, timeAtV);
                futureJoy1 += nextJoy.joy1;
                futureJoy2 += nextJoy.joy2;
            }
            futureJoy1 /= k;
            futureJoy2 /= k;
        }

        double totalJoy1 = spots[u].y1 + futureJoy1;
        double totalJoy2 = spots[u].y2 + futureJoy2;

        visited[u][remainingTime] = true;
        memo[u][remainingTime] = new JoyPair(totalJoy1, totalJoy2);
        return memo[u][remainingTime];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        T = sc.nextInt();

        spots = new Spot[N + 1];
        adj = new ArrayList[N + 1];
        for(int i = 0; i <= N; i++) adj[i] = new ArrayList<>();
        
        memo = new JoyPair[N + 1][T + 1];
        visited = new boolean[N + 1][T + 1];

        for (int i = 1; i <= N; i++) {
            spots[i] = new Spot(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            adj[u].add(new Edge(v, w));
            adj[v].add(new Edge(u, w));
        }

        double totalExpectedJoy1 = 0.0;
        double totalExpectedJoy2 = 0.0;

        for (int i = 1; i <= N; i++) {
            JoyPair result = dfs(i, T);
            totalExpectedJoy1 += result.joy1;
            totalExpectedJoy2 += result.joy2;
        }

        System.out.printf("%.5f %.5f\n", totalExpectedJoy1 / N, totalExpectedJoy2 / N);
    }
}

import sys

# 设置足够大的递归深度
sys.setrecursionlimit(100005)

memo = {}
spots = []
adj = []
N, M, T = 0, 0, 0

def dfs(u, remaining_time):
    if remaining_time < spots[u]['t']:
        return 0.0, 0.0
    
    if (u, remaining_time) in memo:
        return memo[(u, remaining_time)]

    time_after_visit = remaining_time - spots[u]['t']
    
    valid_next_spots = []
    for neighbor, travel_time in adj[u]:
        if time_after_visit >= travel_time + spots[neighbor]['t']:
            valid_next_spots.append((neighbor, travel_time))
            
    future_joy1 = 0.0
    future_joy2 = 0.0
    k = len(valid_next_spots)
    
    if k > 0:
        for v_node, travel_time in valid_next_spots:
            time_at_v = time_after_visit - travel_time
            next_joy1, next_joy2 = dfs(v_node, time_at_v)
            future_joy1 += next_joy1
            future_joy2 += next_joy2
        future_joy1 /= k
        future_joy2 /= k
        
    total_joy1 = spots[u]['y1'] + future_joy1
    total_joy2 = spots[u]['y2'] + future_joy2
    
    memo[(u, remaining_time)] = (total_joy1, total_joy2)
    return total_joy1, total_joy2

def solve():
    global N, M, T, spots, adj, memo
    try:
        line = sys.stdin.readline()
        if not line: return
        N, M, T = map(int, line.split())
        
        spots = [{} for _ in range(N + 1)]
        adj = [[] for _ in range(N + 1)]
        memo = {}

        for i in range(1, N + 1):
            t, y1, y2 = map(int, sys.stdin.readline().split())
            spots[i] = {'t': t, 'y1': y1, 'y2': y2}
            
        for _ in range(M):
            u, v, w = map(int, sys.stdin.readline().split())
            adj[u].append((v, w))
            adj[v].append((u, w))
            
        total_expected_joy1 = 0.0
        total_expected_joy2 = 0.0
        
        for i in range(1, N + 1):
            joy1, joy2 = dfs(i, T)
            total_expected_joy1 += joy1
            total_expected_joy2 += joy2
            
        print(f"{total_expected_joy1 / N:.5f} {total_expected_joy2 / N:.5f}")

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：图上的期望动态规划 (Expectation DP)、记忆化搜索
时间复杂度: $\mathcal{O}(N \cdot T \cdot \text{deg}_{\text{max}})$ ，其中 N 是景点数，T 是总时间， $\text{deg}_{\text{max}}$ 是图中点的最大度数。对于每个状态 (u, t)，我们需要遍历 u 的所有邻居来计算转移，状态总数为 N * T。
空间复杂度: $\mathcal{O}(N \cdot T)$ ，主要用于存储记忆化搜索的 dp 表。