题解

题面描述

外卖骑手需要在给定的起始地点 $S_n$ 和总工作时间 $t$ 内，依次选择若干订单进行配送。每个订单由出发站点 $s$、到达站点 $d$ 和配送费 $p$ 三元组表示，且 $s \ne d$。若同一对 $(s,d)$ 存在多笔订单，可将它们合并，合并后耗时仍为 $1$ 单位，但收入为这批订单费用之和。每次配送无论合并与否，均耗时 $1$，且每笔订单只能配送一次。配送结束条件为工作时间用尽或当前地点无可接订单。输出骑手可获得的最大总收入及对应路径，若多条路径收入相同，则取字典序最小的路径。

思路

1. 合并订单权重
   使用哈希表将每个相同起点 $s$、终点 $d$ 的订单费用相加，得到边权值 $w_{s,d}$。

2. 构建有向图
   以各个地点为节点，存在合并后订单的 $(s,d)$ 对应一条边，边权为 $w_{s,d}$。

3. DFS＋分支定界
   从起点 $S_n$ 出发，深度优先搜索最长路径，状态参数为当前节点 $u$、剩余时间 $r$、已获收入 $v$、当前路径。

   • 若 $r = 0$ 或无可用出边，则更新最优解。
   • 通过预先计算所有边权的降序前缀和，估算上界：$$\text{ub} = v + \sum_{i=1}^{\min(r,\,E)} w_i$$ 若 $\text{ub}$ 小于当前最优收入，则剪枝。
   • 枚举按终点升序排列的出边，保证字典序最小性。
   • 标记已用边，递归后回溯。

4. 复杂度

   • 边数 $E$ 最多为订单数 $M$。
   • 最坏情况下 DFS 搜索分支较多，但分支定界剪枝有效降低了实际搜索量。

cpp

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

int t, sn;
vector<vector<pair<int,int>>> adj; // 邻接表：adj[u] 存储 (v, eid)
vector<ll> w;                      // 每条边的权值 w[eid]
vector<bool> used;                 // 标记边是否已用
vector<ll> pref;                   // 边权降序前缀和
ll bestV = 0;                      // 全局最优收入
vector<int> curP, bestP;           // 当前路径与最优路径

// 深度优先搜索，u=当前节点，rem=剩余时间，val=当前收入
void dfs(int u, int rem, ll val) {
    // 更新最优解（优先收入，其次字典序）
    if (val > bestV || (val == bestV && curP < bestP)) {
        bestV = val;
        bestP = curP;
    }
    if (rem == 0) return;  // 时间耗尽
    // 计算上界：当前收入 + 剩余时间内最大可能收入
    ll ub = val + pref[min(rem, (int)pref.size() - 1)];
    if (ub < bestV) return; // 剪枝

    // 枚举所有出边
    for (auto &pr : adj[u]) {
        int v = pr.first, e = pr.second;
        if (used[e]) continue;      // 边已用不可重复
        used[e] = true;
        curP.push_back(v);
        dfs(v, rem - 1, val + w[e]);
        curP.pop_back();
        used[e] = false;
    }
}

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

    int m;
    cin >> sn >> t >> m;
    map<pair<int,int>, ll> mp;
    // 读入并合并相同起终点的订单费用
    for (int i = 0; i < m; i++) {
        int s, d, p;
        cin >> s >> d >> p;
        mp[{s, d}] += p;
    }
    // 收集所有节点编号，确定图的大小
    set<int> nodes;
    for (auto &kv : mp) {
        nodes.insert(kv.first.first);
        nodes.insert(kv.first.second);
    }
    int maxn = *max_element(nodes.begin(), nodes.end());
    adj.resize(maxn + 1);

    // 构建图
    int eid = 0;
    for (auto &kv : mp) {
        int u = kv.first.first, v = kv.first.second;
        w.push_back(kv.second);
        adj[u].push_back({v, eid});
        eid++;
    }
    used.assign(eid, false);

    // 预处理前缀和（降序）
    vector<ll> ws = w;
    sort(ws.begin(), ws.end(), greater<ll>());
    pref.resize(ws.size() + 1);
    for (int i = 0; i < ws.size(); i++)
        pref[i + 1] = pref[i] + ws[i];

    // 保证遍历出边时按照终点升序，以获取字典序最小路径
    for (int i = 0; i <= maxn; i++)
        sort(adj[i].begin(), adj[i].end());

    // 启动 DFS
    curP.push_back(sn);
    bestP = curP;
    dfs(sn, t, 0);

    // 输出结果
    cout << bestV << "\n";
    for (int i = 0; i < bestP.size(); i++) {
        if (i) cout << " ";
        cout << bestP[i];
    }
    cout << "\n";
    return 0;
}

python

import sys
sys.setrecursionlimit(10**7)

def main():
    sn, t = map(int, sys.stdin.readline().split())
    m = int(sys.stdin.readline())
    mp = {}
    # 合并相同起终点的订单费用
    for _ in range(m):
        s, d, p = map(int, sys.stdin.readline().split())
        mp[(s, d)] = mp.get((s, d), 0) + p

    # 构建节点和邻接表
    nodes = set()
    for (s, d) in mp:
        nodes.add(s); nodes.add(d)
    maxn = max(nodes)
    adj = [[] for _ in range(maxn + 1)]
    w = []
    for eid, ((s, d), cost) in enumerate(mp.items()):
        w.append(cost)
        adj[s].append((d, eid))

    # 标记数组和前缀和
    used = [False] * len(w)
    ws = sorted(w, reverse=True)
    pref = [0] * (len(ws) + 1)
    for i, val in enumerate(ws):
        pref[i + 1] = pref[i] + val

    # 按目标节点升序，确保字典序最小
    for lst in adj:
        lst.sort()

    bestV = 0
    bestP = []
    curP = []

    # DFS 搜索
    def dfs(u, rem, val):
        nonlocal bestV, bestP
        # 更新最优解
        if val > bestV or (val == bestV and curP < bestP):
            bestV, bestP = val, curP.copy()
        if rem == 0:
            return
        # 上界剪枝
        ub = val + pref[min(rem, len(ws))]
        if ub < bestV:
            return
        # 枚举出边
        for v, eid in adj[u]:
            if not used[eid]:
                used[eid] = True
                curP.append(v)
                dfs(v, rem - 1, val + w[eid])
                curP.pop()
                used[eid] = False

    # 启动 DFS
    curP = [sn]
    bestP = [sn]
    dfs(sn, t, 0)

    # 输出
    print(bestV)
    print(" ".join(map(str, bestP)))

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    static int t, sn;
    static List<List<int[]>> adj; // adj.get(u) 存 (v, eid)
    static long[] w;              // 边权
    static boolean[] used;
    static long[] pref;           // 前缀和
    static long bestV = 0;
    static List<Integer> curP = new ArrayList<>(), bestP = new ArrayList<>();

    // DFS 搜索
    static void dfs(int u, int rem, long val) {
        // 更新最优解
        if (val > bestV || (val == bestV && compare(curP, bestP) < 0)) {
            bestV = val;
            bestP = new ArrayList<>(curP);
        }
        if (rem == 0) return;
        // 上界剪枝
        long ub = val + pref[Math.min(rem, pref.length - 1)];
        if (ub < bestV) return;
        // 枚举出边
        for (int[] e : adj.get(u)) {
            int v = e[0], eid = e[1];
            if (!used[eid]) {
                used[eid] = true;
                curP.add(v);
                dfs(v, rem - 1, val + w[eid]);
                curP.remove(curP.size() - 1);
                used[eid] = false;
            }
        }
    }

    // 列表字典序比较
    static int compare(List<Integer> a, List<Integer> b) {
        int n = Math.min(a.size(), b.size());
        for (int i = 0; i < n; i++) {
            if (!a.get(i).equals(b.get(i)))
                return a.get(i) - b.get(i);
        }
        return a.size() - b.size();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        sn = in.nextInt();
        t = in.nextInt();
        int m = in.nextInt();
        Map<String, Long> mp = new HashMap<>();
        // 合并订单费用
        for (int i = 0; i < m; i++) {
            int s = in.nextInt(), d = in.nextInt(), p = in.nextInt();
            String key = s + "#" + d;
            mp.put(key, mp.getOrDefault(key, 0L) + p);
        }
        // 构建图
        Set<Integer> nodes = new HashSet<>();
        for (String key : mp.keySet()) {
            String[] sp = key.split("#");
            nodes.add(Integer.parseInt(sp[0]));
            nodes.add(Integer.parseInt(sp[1]));
        }
        int maxn = Collections.max(nodes);
        adj = new ArrayList<>();
        for (int i = 0; i <= maxn; i++) adj.add(new ArrayList<>());
        w = new long[mp.size()];
        int eid = 0;
        for (Map.Entry<String, Long> e : mp.entrySet()) {
            String[] sp = e.getKey().split("#");
            int s = Integer.parseInt(sp[0]), d = Integer.parseInt(sp[1]);
            w[eid] = e.getValue();
            adj.get(s).add(new int[]{d, eid});
            eid++;
        }
        used = new boolean[eid];
        // 前缀和
        long[] ws = Arrays.stream(w).boxed()
                          .sorted(Comparator.reverseOrder())
                          .mapToLong(Long::longValue)
                          .toArray();
        pref = new long[ws.length + 1];
        for (int i = 0; i < ws.length; i++) {
            pref[i + 1] = pref[i] + ws[i];
        }
        // 保证终点升序
        for (List<int[]> lst : adj) {
            lst.sort(Comparator.comparingInt(a -> a[0]));
        }
        // 启动 DFS
        curP.add(sn);
        bestP.add(sn);
        dfs(sn, t, 0);
        // 输出
        System.out.println(bestV);
        for (int i = 0; i < bestP.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(bestP.get(i));
        }
        System.out.println();
    }
}

题目内容

外卖骑手是一个和时间赛跑的工作。由于外卖订单一般集中在一日三餐的时间，具有时间短突发量大的特点，骑手们需要在订单集中的时间段内尽可能送出更多的订单以获得更多的收入。

骑手的工作流程大致是这样的，从一个商家出发，选择一个订单，送到目的地点，在目的地点接新的订单送到下一个目的地，如此循环。一个订单只能配送一次，骑手不能重复配送相同的订单。

从出发地点到取的地点的一次配送需要消耗1单位的时间。同一个地点可能发出多笔订单，其中一些订单可能要送往同一个目的地，这些起点和终点相同的订单可以合并配送，合并配送的多笔订单和单笔订单一样都只消耗1单位的时间。

简化起见，我们不区分商家和配送目的地点，统一视作地图上的一个地点。骑手的工作时间总时间是给定的，如果剩余的工作时间为0，则配送工作结束;如果到达目的地点之后，没有再从该地点发出的订单，则配送工作结束。

假设地图上有$N$个地点，每个地点有$[0,X]$个待送出的订单，每个订单以$[s,d,f]$来表示，一共有$M$个订单。其中$s$是出发站点编号，$d$是目的站点编号，$p$是这笔订单的配送费，约定$s\ !=d$。给定骑手的出发地点编号$S_n$和工作总时间$t$，请计算出骑手最多能获得的收入。

具体每个取值的范围说明:

输入描述

第1行为空格分隔的$2$个整数，分别表示骑手的出发地点编号$S_n$和工作总时间$t$；

第$2$行为一个表示订单数量的整数$M$;

第$3$行开始的$M$行每行都是以空格分隔的$3$个整数$s,d$和$p,s$表示出发站点，$d$表示目标站点，$p$表示订单收入。

输出描述

第$1$行是一个整数，表示骑手能获得的最多的收入;

第$2$行是空格分隔的整数数组，每个数字是一个地点编号，表示从开始到结束的配送路径。当多个路径能够获取相同的收入时，输出从前往后数字序最小的路径。

样例1

输入

0 2
6
0 1 2
0 5 3
5 3 3
1 2 3
2 4 10
1 3 4

输出

6
0 1 3

说明

如图所示：

工作时间$t$为$2$的条件下，从$0$出发，节点$4$不可达，可选的线路是:

$1，0->1->3$收入是$2+4=6$

$2，0->5->3$收入是$3+3=6$

$2，0->1->2$收入是$2+3=5$

线路$1$和线路$2$的收入最大，都是$6$，选择数字序最小的路径$0->1->3$,输出总收入$6$和线路$0\ 1\ 3$

样例2

输入

3 2
5 
3 4 10
4 5 5
4 5 10
4 5 15
5 6 20

输出

40
3 4 5

说明

如图所示：

工作时间$t$为$2$的条件下，可以进行$2$次配送，其中从$3$到$4$消耗$1$的时间，可以获取收入$10$。从$4$到$5$有$3$个订单，这$3$个订单的起终点相同(都是从$4$到$5$)，可以合并配送，收入$5+10+15=30$，只消耗$1$的时间。

所以唯一的路线是$3->4->5$，总收入为$10+30=40$

样例3

输入

1 2
5 
1 2 5
2 3 10
2 3 8
2 4 6
4 5 6

输出

23
1 2 3

说明

如图所示：

工作时间$t$为$2$的条件下，从$1$出发，可选的线路是: $1，1->2->3$ 注意从$1$到$3$有$2$个要配送的外卖，可以合并配送，时间只算$1$，所以总收入是$5+8+10=23$

$2，1->2->4$收入是$5+6=11$

线路$1$的收入最大，选择线路$1$，输出总收入$23$和线路$0\ 1\ 3$