小红的旅游攻略

[题目链接](https://www.nowcoder.com/practice/75744bcb2731427393cf65e513a27a68)

思路

小红最多选择 3 个相邻的景点，按顺序写进攻略。总时间（浏览时间 + 交通时间）不超过 $T$ ，要使总价值最大。

分情况讨论

由于最多选 3 个景点，我们可以按选择的景点数量分三种情况枚举：

情况一：选 1 个景点 $i$

总花费为 $t_i$ ，总价值为 $v_i$ 。遍历所有景点即可。

情况二：选 2 个相邻景点 $i, j$

枚举每条边 $(i, j, w)$ ，总花费为 $t_i + t_j + w$ ，总价值为 $v_i + v_j$ 。

情况三：选 3 个景点 $a \to b \to c$

三个景点形成一条路径 $a - b - c$ ，其中 $b$ 是中间节点， $(a, b)$ 和 $(b, c)$ 都是图中的边。

总花费 = $t_a + t_b + t_c + \text{dist}(a, b) + \text{dist}(b, c)$ ，总价值 = $v_a + v_b + v_c$ 。

情况三的高效处理

枚举中间节点 $b$ ，剩余预算为 $\text{budget} = T - t_b$ 。对 $b$ 的每个邻居 $x$ ，定义其"代价"为 $\text{cost}_x = t_x + \text{dist}(x, b)$ 。问题转化为：从 $b$ 的邻居中选两个不同的邻居 $a, c$ ，使得 $\text{cost}_a + \text{cost}_c \le \text{budget}$ ，且 $v_a + v_c$ 最大。

排序 + 前缀最大值 + 二分查找：

将 $b$ 的所有可行邻居按代价排序。
维护前缀最大值（记录 Top-2 的值和索引），方便在排除当前元素时取次大值。
对每个邻居 $a$ ，二分查找代价不超过 $\text{budget} - \text{cost}_a$ 的最大范围，从前缀 Top-2 中取出不与 $a$ 重复的最大价值。

样例演示

输入：4 个景点， $T = 8$ 。

路线 $3 \to 2 \to 1$ ：

浏览时间： $t_3 + t_2 + t_1 = 3 + 2 + 1 = 6$
交通时间： $\text{dist}(3,2) + \text{dist}(2,1) = 1 + 1 = 2$
总时间 $= 8 \le T$ ，总价值 $= v_3 + v_2 + v_1 = 2 + 3 + 4 = 9$

复杂度分析

时间复杂度： $O(n + m \log m)$ 。情况一 $O(n)$ ，情况二 $O(m)$ ，情况三中每个邻居在枚举中间节点时被处理一次（排序 + 二分），总复杂度为 $O(\sum_{b} d_b \log d_b) = O(m \log m)$ 。
空间复杂度： $O(n + m)$ ，存储图的邻接表。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    long long T;
    cin >> n >> m >> T;

    vector<long long> v(n+1), t(n+1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    for(int i = 1; i <= n; i++) cin >> t[i];

    vector<vector<pair<int,long long>>> adj(n+1);
    for(int i = 0; i < m; i++){
        int a, b;
        long long w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    long long ans = 0;

    // 情况一：选 1 个景点
    for(int i = 1; i <= n; i++){
        if(t[i] <= T){
            ans = max(ans, v[i]);
        }
    }

    // 情况二：选 2 个相邻景点
    for(int u = 1; u <= n; u++){
        for(auto &[nb, w] : adj[u]){
            long long cost = t[u] + t[nb] + w;
            if(cost <= T){
                ans = max(ans, v[u] + v[nb]);
            }
        }
    }

    // 情况三：选 3 个景点 a-b-c，枚举中间节点 b
    for(int b = 1; b <= n; b++){
        long long budget = T - t[b];
        if(budget < 0) continue;
        if((int)adj[b].size() < 2) continue;

        // 收集可行邻居：(代价, 价值)
        vector<pair<long long, long long>> nbs;
        for(auto &[nb, w] : adj[b]){
            long long c = t[nb] + w;
            if(c <= budget){
                nbs.push_back({c, v[nb]});
            }
        }
        if((int)nbs.size() < 2) continue;

        sort(nbs.begin(), nbs.end());
        int sz = nbs.size();

        // 前缀 Top-2：记录最大值和次大值及其索引
        struct Top2 {
            long long v1, v2;
            int i1, i2;
        };
        vector<Top2> pre(sz);
        pre[0] = {nbs[0].second, -1, 0, -1};
        for(int i = 1; i < sz; i++){
            long long val = nbs[i].second;
            if(val >= pre[i-1].v1){
                pre[i] = {val, pre[i-1].v1, i, pre[i-1].i1};
            } else if(val > pre[i-1].v2){
                pre[i] = {pre[i-1].v1, val, pre[i-1].i1, i};
            } else {
                pre[i] = pre[i-1];
            }
        }

        for(int i = 0; i < sz; i++){
            long long rem = budget - nbs[i].first;
            if(rem < 0) break;
            // 二分查找代价不超过 rem 的最大索引
            int lo = 0, hi = sz - 1, best_j = -1;
            while(lo <= hi){
                int mid = (lo + hi) / 2;
                if(nbs[mid].first <= rem){
                    best_j = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            if(best_j < 0) continue;

            // 在 [0..best_j] 中取不等于 i 的最大价值
            long long best_val = -1;
            if(pre[best_j].i1 != i){
                best_val = pre[best_j].v1;
            } else {
                best_val = pre[best_j].v2;
            }
            if(best_val < 0) continue;
            ans = max(ans, v[b] + nbs[i].second + best_val);
        }
    }

    cout << ans << endl;
    return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);

        in.nextToken(); int n = (int)in.nval;
        in.nextToken(); int m = (int)in.nval;
        in.nextToken(); long T = (long)in.nval;

        long[] v = new long[n+1];
        long[] t = new long[n+1];
        for(int i = 1; i <= n; i++) { in.nextToken(); v[i] = (long)in.nval; }
        for(int i = 1; i <= n; i++) { in.nextToken(); t[i] = (long)in.nval; }

        @SuppressWarnings("unchecked")
        List<long[]>[] adj = new ArrayList[n+1];
        for(int i = 0; i <= n; i++) adj[i] = new ArrayList<>();

        for(int i = 0; i < m; i++){
            in.nextToken(); int a = (int)in.nval;
            in.nextToken(); int b = (int)in.nval;
            in.nextToken(); long w = (long)in.nval;
            adj[a].add(new long[]{b, w});
            adj[b].add(new long[]{a, w});
        }

        long ans = 0;

        // 情况一：选 1 个景点
        for(int i = 1; i <= n; i++){
            if(t[i] <= T) ans = Math.max(ans, v[i]);
        }

        // 情况二：选 2 个相邻景点
        for(int u = 1; u <= n; u++){
            for(long[] e : adj[u]){
                int nb = (int)e[0]; long w = e[1];
                long cost = t[u] + t[nb] + w;
                if(cost <= T) ans = Math.max(ans, v[u] + v[nb]);
            }
        }

        // 情况三：选 3 个景点 a-b-c，枚举中间节点 b
        for(int b = 1; b <= n; b++){
            long budget = T - t[b];
            if(budget < 0) continue;
            if(adj[b].size() < 2) continue;

            List<long[]> nbs = new ArrayList<>();
            for(long[] e : adj[b]){
                int nb = (int)e[0]; long w = e[1];
                long c = t[nb] + w;
                if(c <= budget) nbs.add(new long[]{c, v[nb]});
            }
            if(nbs.size() < 2) continue;

            nbs.sort((a2, b2) -> Long.compare(a2[0], b2[0]));
            int sz = nbs.size();

            // 前缀 Top-2
            long[] preV1 = new long[sz], preV2 = new long[sz];
            int[] preI1 = new int[sz];
            preV1[0] = nbs.get(0)[1]; preV2[0] = -1; preI1[0] = 0;
            for(int i = 1; i < sz; i++){
                long val = nbs.get(i)[1];
                if(val >= preV1[i-1]){
                    preV1[i] = val; preI1[i] = i;
                    preV2[i] = preV1[i-1];
                } else if(val > preV2[i-1]){
                    preV1[i] = preV1[i-1]; preI1[i] = preI1[i-1];
                    preV2[i] = val;
                } else {
                    preV1[i] = preV1[i-1]; preI1[i] = preI1[i-1];
                    preV2[i] = preV2[i-1];
                }
            }

            for(int i = 0; i < sz; i++){
                long rem = budget - nbs.get(i)[0];
                if(rem < 0) break;
                int lo = 0, hi = sz - 1, bestJ = -1;
                while(lo <= hi){
                    int mid = (lo+hi)/2;
                    if(nbs.get(mid)[0] <= rem){ bestJ = mid; lo = mid+1; }
                    else hi = mid-1;
                }
                if(bestJ < 0) continue;
                long bestVal;
                if(preI1[bestJ] != i) bestVal = preV1[bestJ];
                else bestVal = preV2[bestJ];
                if(bestVal < 0) continue;
                ans = Math.max(ans, v[b] + nbs.get(i)[1] + bestVal);
            }
        }

        System.out.println(ans);
    }
}