不知道取什么名字的题目2 - 题解

标签与难度

标签: 0-1分数规划, 二分答案, 图论, SPFA, 差分约束, 反向建图, 事件图

难度: 2300

题目大意喵~

各位旅行者，大家好喵~！这次我们要解决一个关于星际旅行的超有趣问题！

想象一下，在一个每天有 $h$ 小时的歪歪星球上，有 $n$ 座城市和 $m$ 条单向的列车线路。每条线路都像一个魔法传送门，它会在特定的时间 $t_1$ 从城市 $u$ 出发，经过 $t_2$ 小时后把你送到城市 $v$ ，还能让你获得 $val$ 点的舒适度呢！

现在，有 $k$ 位旅行者，他们都想去终点城市 $n$ 。旅行的代价可不只是车票钱哦，还要计算 等待时间 和 乘车时间 的总成本。公式是这样的：

\text{总成本} = (\text{总等待时间} \times a) + (\text{总乘车时间} \times b)

我们的目标是，设计一个最棒的旅行策略，让所有成功到达终点的乘客们，他们的 总舒适度之和 与 总时间成本之和 的比率达到最大！也就是最大化下面这个可爱的分数，喵~

\frac{\sum \text{舒适度}}{\sum \text{总时间成本}}

解题思路分析

呜喵~ 这个问题看起来好复杂，又要计算时间，又要计算舒适度，还要算比率！但是不要怕，让我来把复杂的问题拆解成一小步一小步，你就会发现它的核心思想其实非常巧妙哦！

第一步：把“求最大比率”变成“猜答案”！(0-1分数规划)

直接去求一个分数的最大值是很难的，对吧？那我们换个思路，我们来玩“猜数字”的游戏，喵~

我们猜一个比率，比如说 x，然后我们来判断：“我们能不能找到一种旅行方案，让最终的 $\frac{\sum \text{舒适度}}{\sum \text{总成本}} \ge x$ 呢？”

这个不等式可以变身哦！看我变！

\sum \text{舒适度} \ge x \cdot \sum \text{总成本}

再变！

\sum \text{舒适度} - x \cdot \sum \text{总成本} \ge 0

看！我们把一个除法问题，变成了一个加减法问题！我们只需要判断，是否存在一种走法，让所有“收益”减去“加权成本”之后，总和能大于等于0。

如果对于我们猜的 x，能找到这样的方案，说明 x 是个可行的答案，我们就可以更大胆一点，猜一个更大的 x！如果找不到，说明我们太贪心啦，猜的 x 太大了，得往小了猜。这不就是经典的 二分答案 嘛，喵~

第二步：把“时空旅行”变成“图上漫步”！(事件图建模)

好啦，现在我们的核心任务是实现那个 check(x) 函数，也就是判断 $\sum (\text{舒适度} - x \cdot \text{成本}) \ge 0$ 是否可能。

城市之间的移动有时间先后，这怎么表示呢？当当当当~ 答案就是构建一个神奇的 事件图！

图里的点点是什么？
- 列车节点：每一趟列车，我们都把它看作一个点。当你“在”这个点上，就意味着你正在这趟列车上旅行。
- 事件节点：在一个城市里，每一次“有车到达”或者“有车出发”，都是一个重要的“事件”。我们把这些事件也看作图里的点。
图里的边边和权重呢？ 边就是这些状态之间的转换，而权重就是我们变身后的公式 收益 - x * 成本！
1. 下车！ 从“列车节点”连一条边到这趟车对应的“到达事件节点”。
  - 权重是：列车舒适度 - x * 乘车时间 * b
2. 等待... 在同一个城市里，从一个事件，连一条边到按时间顺序的下一个事件。
  - 权重是：0 - x * 等待时间 * a (呜，等待没有收益，只有成本)
3. 上车！ 从一个“出发事件节点”连一条边到它对应的“列车节点”。
  - 权重是：0 (上车动作本身不花时间，也没有收益)

第三步：寻找最棒的路径！(反向图 + SPFA)

现在，我们的问题就变成了：在这个事件图里，能不能找到一条路径，让它的总权重之和大于等于0？这其实就是在找图里的 最长路！

但我们有很多个起点，一个个出发去找太慢了。聪明的我有妙招：把地图倒过来看！我们把所有边的方向都反过来，然后从 终点城市的所有“到达事件” 出发，只跑一次 SPFA算法！

为什么要用SPFA呀？ 因为我们的边权有正有负，Dijkstra酱处理不了。而且，图里可能出现“正权环”，也就是一个可以无限刷分的小圈圈！SPFA可以完美地发现这种情况，一旦发现，就说明我们找到了一个可以让总收益无限大的方案，那 check(x) 肯定是通过啦！
倒过来看有什么好处？ 从终点出发跑一次，我们就能知道所有节点到终点的最长距离了！然后我们只需要检查一下，对于每个乘客的初始状态，他们到终点的最长路是不是大于等于0，就知道这个 x 可不可行啦！

第四步：让算法更优雅！(逻辑优化)

在跑SPFA之前，我们其实需要先剪掉一些无用的路径，只在那些“确定能到达某个起点的节点”上跑。

一个聪明的优化是：我们想知道“哪些节点能到达终点集合”，这等价于在图的转置上，“从终点集合出发能到达哪些节点”。我们可以在建图的同时，顺手建立一个转置图，然后从所有逻辑终点（原图的起点）出发，做一次BFS，就能高效地标记出所有有用的节点啦！

总结一下我们最终的攻略，喵~

二分答案 x。（因为check函数开销大，我们采用精度控制的while循环来代替固定次数迭代，以减少总运行时间！）
对于每个 x，构建一个带权重的 事件图 和它的 转置图。
在转置图上做一次BFS，预处理出所有能到达终点的节点。
在 反向的 事件图上，从终点出发跑 SPFA 找最长路（只考虑有用的节点）。
根据最长路的结果判断 check(x) 是否成功，然后调整二分范围。

是不是感觉清晰多啦？喵~

代码实现

这是我根据最终优化思路，精心打磨出的全新代码哦！它使用了面向对象的思想，把所有逻辑都封装在一个 ProblemSolver 类里，数据结构和算法实现都非常现代化，希望能帮助你更好地理解这个过程，呐！

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>

class ProblemSolver {
private:
    // --- 常量定义 ---
    static const int MAX_NODES = 3009;
    static const int MAX_CITIES = 1009;

    // --- 结构体定义 ---
    struct Edge {
        int to;
        int val;
        long long ff_val;
    };

    enum EventType {
        ARRIVAL = 0,
        DEPARTURE = 1
    };

    struct Event {
        int time, type, train_id;
    };

    // --- 核心数据 ---
    int num_cities, num_train_lines, hours_in_day, num_passengers, wait_cost_per_hour, travel_cost_per_hour;
    int node_counter;
    
    // --- 图和状态数组 ---
    std::vector<std::vector<Edge>> adj;
    std::vector<std::vector<int>> adj_rev; // adj的转置图
    std::vector<std::vector<Event>> city_events;
    std::vector<long long> vx;
    std::vector<long double> dist;
    std::vector<int> is_start_city;
    std::vector<int> spfa_queue_count;
    std::vector<int> can_reach_destination;
    std::vector<int> visited_in_reachability_check;
    std::vector<int> is_spfa_start_node;
    std::vector<int> in_spfa_queue;
    std::vector<int> train_comfort;
    std::vector<int> train_travel_time;
    std::vector<int> is_logical_destination;

    static bool compare_events(Event x, Event y) {
        if (x.time == y.time) return x.type < y.type;
        return x.time < y.time;
    }

    void add_reverse_edge(int u, int v, int w, long long ff_w) {
        // adj是反向图，所以加的是 v -> u 的边
        std::swap(u, v);
        adj[u].push_back({v, w, ff_w});
        // adj_rev是adj的转置图，所以加的是 u -> v 的边
        adj_rev[v].push_back(u);
    }

    void read_input() {
        std::cin >> num_cities >> num_train_lines >> hours_in_day >> num_passengers >> wait_cost_per_hour >> travel_cost_per_hour;
        for (int i = 1; i <= num_passengers; i++) {
            int x;
            std::cin >> x; is_start_city[x] = 1;
        }
        for (int i = 1; i <= num_train_lines; i++) {
            int u, v, a, b, c;
            std::cin >> u >> v >> a >> b >> c;
            city_events[v].push_back({(a + b) % hours_in_day, ARRIVAL, i});
            city_events[u].push_back({a, DEPARTURE, i});
            train_comfort[i] = c;
            train_travel_time[i] = b;
        }
    }

    void build_graph() {
        node_counter = num_train_lines;
        for (int i = 1; i <= num_cities; i++) {
            std::sort(city_events[i].begin(), city_events[i].end(), compare_events);
            if (is_start_city[i] == 1 && (!city_events[i].empty())) {
                is_logical_destination[node_counter + 1] = 1;
                vx[node_counter + 1] = -1ll * city_events[i][0].time * wait_cost_per_hour;
            }
            for (int j = 0; j < city_events[i].size(); j++) {
                int s1 = j, s2 = (j + 1) % city_events[i].size();
                int u_node = node_counter + s1 + 1;
                int v_node = node_counter + s2 + 1;
                long long wait_ff = -1ll * (city_events[i][s2].time - city_events[i][s1].time + hours_in_day) % hours_in_day * wait_cost_per_hour;
                add_reverse_edge(u_node, v_node, 0, wait_ff);
                if (city_events[i][j].type == ARRIVAL) {
                    long long travel_ff = -1ll * travel_cost_per_hour * train_travel_time[city_events[i][j].train_id];
                    add_reverse_edge(city_events[i][j].train_id, u_node, train_comfort[city_events[i][j].train_id], travel_ff);
                    if (i == num_cities) is_spfa_start_node[u_node] = 1;
                } else {
                    add_reverse_edge(u_node, city_events[i][j].train_id, 0, 0);
                }
            }
            node_counter += city_events[i].size();
        }
    }

    void preprocess_reachability() {
        // 优化：要找到所有能在adj图中“到达”逻辑终点的节点，
        // 我们可以在adj的“转置图”(adj_rev)上，从所有逻辑终点出发进行一次图遍历。
        std::queue<int> q;
        std::fill(can_reach_destination.begin(), can_reach_destination.end(), 0);

        // 将所有逻辑终点（即原图的起点）作为多源BFS的起点
        for (int i = 1; i <= node_counter; ++i) {
            if (is_logical_destination[i]) {
                q.push(i);
                can_reach_destination[i] = 1;
            }
        }

        // 在转置图(adj_rev)上进行BFS
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : adj_rev[u]) {
                if (!can_reach_destination[v]) {
                    can_reach_destination[v] = 1;
                    q.push(v);
                }
            }
        }
    }

    bool check(long double x) {
        std::fill(dist.begin(), dist.end(), -(long double)100000000000000000000.0);
        std::fill(in_spfa_queue.begin(), in_spfa_queue.end(), 0);
        std::fill(spfa_queue_count.begin(), spfa_queue_count.end(), 0);
        std::queue<int> q;
        for (int i = 1; i <= node_counter; i++) {
            if (is_spfa_start_node[i] && can_reach_destination[i]) {
                in_spfa_queue[i] = 1;
                dist[i] = 0;
                q.push(i);
            }
        }
        while (!q.empty()) {
            int a = q.front();
            in_spfa_queue[a] = 0;
            spfa_queue_count[a]++;
            q.pop();
            if (spfa_queue_count[a] > node_counter) return 1;
            for (const auto& edge : adj[a]) {
                if (can_reach_destination[edge.to] && dist[edge.to] < dist[a] + edge.val + edge.ff_val * x) {
                    dist[edge.to] = dist[a] + edge.val + edge.ff_val * x;
                    if (!in_spfa_queue[edge.to]) {
                        q.push(edge.to);
                        in_spfa_queue[edge.to] = 1;
                    }
                }
            }
        }
        for (int i = 1; i <= node_counter; i++) {
            if (is_logical_destination[i] && dist[i] + vx[i] * x >= 0) return 1;
        }
        return 0;
    }

    void binary_search_for_answer() {
        long double l = 0, r = 1000000000;
        // 实践发现，对于这道题，check函数开销较大，固定的100次迭代会导致超时。
        // 因此改用精度控制的while循环，当答案区间的长度小于一个极小值(epsilon)时停止。
        // 这样迭代次数会减少到大约60次，足以在时限内通过！
        while (r - l > 1e-8) {
            long double mid = l + (r - l) / 2;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        std::cout << std::fixed << std::setprecision(12) << l << std::endl;
    }

public:
    ProblemSolver() : node_counter(0) {
        // 使用 resize 初始化所有 vector
        adj.resize(MAX_NODES);
        adj_rev.resize(MAX_NODES);
        city_events.resize(MAX_CITIES);
        vx.resize(MAX_NODES, 0);
        dist.resize(MAX_NODES, 0);
        is_start_city.resize(MAX_CITIES, 0);
        spfa_queue_count.resize(MAX_NODES, 0);
        can_reach_destination.resize(MAX_NODES, 0);
        visited_in_reachability_check.resize(MAX_NODES, 0);
        is_spfa_start_node.resize(MAX_NODES, 0);
        in_spfa_queue.resize(MAX_NODES, 0);
        train_comfort.resize(MAX_CITIES, 0);
        train_travel_time.resize(MAX_CITIES, 0);
        is_logical_destination.resize(MAX_NODES, 0);
    }

    void solve() {
        read_input();
        build_graph();
        preprocess_reachability();
        binary_search_for_answer();
    }
};

// 主函数
signed main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ProblemSolver solver;
    solver.solve();
    
    return 0;
}

复杂度分析

时间复杂度: $O(L \cdot (N+M))$ ，其中 $L$ 是二分答案的次数（通常是一个较大的常数，比如100）， $N$ 是事件图中的节点总数， $M$ 是事件图中的边总数。由于我们优化了可达性预处理，SPFA的期望复杂度是 $O(k(N+M))$ ，其中 $k$ 是个小常数，但在最坏情况下（如果出题人特意构造数据卡SPFA），复杂度会退化。不过对于大多数情况，这个解法是足够高效的。
空间复杂度: $O(N+M)$ ，主要是存储事件图的邻接表、转置图以及各种状态数组所占用的空间。

知识点总结

0-1分数规划: 解决“最大化比率”问题的利器，核心思想是二分答案，将问题转化为判定问题。
图论建模: 面对复杂的状态和转移关系时，学会构建抽象的图模型（如此题的“事件图”）是解决问题的关键一步。
SPFA算法: 在带权有向图中求单源最短/最长路，尤其擅长处理带有负权边（或正权边求最长路）和检测负权环（或正权环）的场景。
反向图/转置图思想: 当遇到“多点到一个点”或者需要判断可达性时，可以尝试在反向或转置图上进行遍历，从而简化计算，提高效率。

希望这篇题解能让你彻底明白这道题的奥秘，喵~！如果还有不懂的地方，随时可以来问我哦！

不知道取什么名字的题目2 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：把“求最大比率”变成“猜答案”！(0-1分数规划) ​

第二步：把“时空旅行”变成“图上漫步”！(事件图建模) ​

第三步：寻找最棒的路径！(反向图 + SPFA) ​

第四步：让算法更优雅！(逻辑优化) ​

代码实现 ​

复杂度分析 ​

知识点总结 ​