野餐规划

形式化题目

给一张无向带权图：节点是若干人（不超过 20 人）和公园 Park，每条边有长度 $L$ ，保证每个人都能（直接或间接）到达 Park。

一辆车的行驶过程是：从某个人的家出发，沿边行驶，途中可以经过其他人的家并把他们全部收上车（车容量无限），最终开进 Park。车一旦进入 Park 就停在那里，不能再开出接人。Park 最多停 $s$ 辆车。

所有人都要到达 Park。求所有汽车行驶路程总和的最小值。

正解

思路

第一步：把问题翻译成生成树

「车一旦进公园就必须停下」意味着：每辆车最终对应一条从某人的家到 Park 的路径，车上所有人挤在一起沿这条路径走。把每个人看作树上的一个点、每条被走过的道路看作一条树边，则：

一个合法方案恰好对应一棵包含 Park 的生成树；
总里程 = 树上所有边的权值和；
停车数 = 树上与 Park 相连的边数（每条公园边都是一辆车开进公园的"最后一公里"）。

于是题目变成经典模型：求包含 Park 的生成树中边权和最小、且 Park 的度数 $\leqslant s$ 的一棵——度限制最小生成树。

第二步：先不管限制，缩掉公园跑 MST

先看 $s$ 足够大（度数不受限）时怎么做。把 Park 和它的所有关联边删掉，剩下的图会被分成若干连通块。观察两点：

每个连通块内部：块内所有人怎么互相连接，与公园无关，直接对人—人边跑 Kruskal 求最小生成森林即可；
每个连通块必须有一条边接入 Park（否则块里的人到不了公园），而且只需一条：车先开到块内某个人的家，沿块内的生成树边绕一圈把所有人收齐，再从任意一点开进公园。所以每个块取最便宜的那条公园边接入。

此时设原图（去掉 Park 后）有 $k$ 个连通块，得到一棵 Park 度数恰为 $k$ 、总边权和最小的生成树，停车数正好 $k$ 。

对样例（ $s=3$ ）具体算一遍。去掉 Park 后对人—人边跑 Kruskal，按权依次选中 $32,43,79,82$ （ $90$ 会被 $82+79$ 成环跳过、 $109$ 更大），五个人的家连成一个连通块；再接上最便宜的公园边 Bernardo-Park 19。得到度数 $k=1$ 的最优树，总里程 $32+43+79+82+19=255$ （这正好也是 $s=1$ 时的答案）。

graph LR
    P((Park)) ---|19| B((Bernardo))
    B ---|32| A((Alphonzo))
    A ---|43| E((Eduardo))
    E ---|79| H((Herb))
    B ---|82| C((Clemenzi))

上图是第二步结束时的形状：Park 度数为 $1$ ，Bernardo 的车从自己家出发，沿 $32\to43\to79$ 收齐 Alphonzo、Eduardo、Herb，再沿 $82$ 收 Clemenzi，最后开进公园（ $19$ ）。

第三步：用剩余车位做「交换」

若 $k<s$ ，可以再停一辆车：让某个人 $v$ 自己直接开去公园。具体操作是：

往树里加一条公园边 $v\text{-}Park$ ，权 $w$ ——树上出现一个环；
删掉 $v \to Park$ 树上路径中最重的一条非公园边 $w'$ ，恢复成树。

总里程变化 $\Delta = w - w'$ 。 $\Delta<0$ 就变便宜了。每次在所有公园边里选 $\Delta$ 最小的交换执行，直到停满 $s$ 辆车，或者没有负收益的交换（此时继续停车只会更贵，提前停止）。

为什么逐次交换就是最优的？这是度限制最小生成树的经典交换引理：若 $T$ 是度数为 $d-1$ 的最优树， $T'$ 是度数为 $d$ 的最优树，则存在一条 $T'$ 有而 $T$ 没有的公园边，把它的"加边 + 删路径最重非公园边"交换作用到 $T$ 上，能恰好得到一棵度数为 $d$ 的最优树。于是从度数 $k$ 的最优树出发，逐次做最优交换，就依次得到度数 $k+1,k+2,\dots$ 下的最优树。

两个实现细节：

找"路径最重的非公园边"时不比较公园边——删掉公园边不会让公园度数加一，起不到多停一辆车的作用；
$v$ 自己就是所在块"接入公园的那个人"（单人块）时，路径上没有非公园边可删，这种交换只会让同一辆车翻倍占两个车位，直接跳过。

继续样例： $s=3$ 还剩两个车位。

试 Herb-Park 24：树上路径 $Herb\to Eduardo\to Alphonzo\to Bernardo\to Park$ 中最重非公园边是 $79$ ， $\Delta=24-79=-55$ ，总里程 $255-55=200$ ；
再试 Clemenzi-Park 65：此时路径 $Clemenzi\to Bernardo\to Park$ 中最重非公园边是 $82$ ， $\Delta=65-82=-17$ ，总里程 $200-17=183$ 。

剩下的交换（如 Eduardo-Park 57 换 $43$ ， $\Delta=14$ ）都非负收益，停止。答案 $183$ ，与样例输出一致。用暴力枚举全部生成树核对： $s=1$ 时最优 $255$ 、 $s=2$ 时 $200$ 、 $s=3$ 时 $183$ ，与逐次交换的结果完全吻合。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:30
 * update_at: 2026-10-10 13:30
 */

// 野餐规划：度限制最小生成树。缩掉 Park 跑 Kruskal，每块接最便宜的公园边，
// 再用剩余车位反复做「加公园边、删路径最重非公园边」的最优交换。
#include <algorithm>
#include <cstdio>
#include <map>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

const int PARK = 0;   // 公园固定编号为 0，人按出现顺序从 1 开始
const int MAXN = 105; // 人数不超过 20，节点总数留足余量

struct Edge { // 一条边：(权值, 端点 a, 端点 b)
    int w, a, b;
};

struct Node { // 树上路径扫描的栈元素
    int u, parent, wmx, eidx;
};

map<string, int> nameId; // 名字 -> 编号
int fa[MAXN];            // 并查集
int nodeCnt;             // 节点总数（含公园）
int chW[MAXN];           // 每个连通块用的最便宜公园边权
int chV[MAXN];           // 该公园边接的人
bool hasCh[MAXN];        // 该连通块是否已经接入
vector<int> roots;       // 连通块根的首次出现顺序
vector<Edge> roadE;      // 人—人边
vector<Edge> linkE;      // 人—公园边，存在 (w, 人, PARK)
vector<Edge> treeE;      // 当前生成树的边
vector<vector<int> > adj; // 邻接表，存 treeE 的下标
vector<Node> stk;

int findRoot(int x) { // 并查集查找（路径减半）
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

int ident(const string &name) { // 名字 -> 编号，新名字按出现顺序编号
    map<string, int>::iterator it = nameId.find(name);
    if (it != nameId.end()) return it->second;
    int id = nameId.size();
    nameId[name] = id;
    return id;
}

bool cmpEdge(const Edge &x, const Edge &y) { // 按 (权, a, b) 字典序
    if (x.w != y.w) return x.w < y.w;
    if (x.a != y.a) return x.a < y.a;
    return x.b < y.b;
}

int worstOnPath(int src) { // src 到公园的树上路径中最重的非公园边，返回下标；没有则 -1
    adj.assign(nodeCnt, vector<int>());
    for (int i = 0; i < (int)treeE.size(); ++i) {
        adj[treeE[i].a].push_back(i);
        adj[treeE[i].b].push_back(i);
    }
    stk.clear();
    Node s;
    s.u = src; s.parent = PARK; s.wmx = -1; s.eidx = -1;
    stk.push_back(s);
    while (!stk.empty()) {
        Node cur = stk.back();
        stk.pop_back();
        for (int k = 0; k < (int)adj[cur.u].size(); ++k) {
            int idx = adj[cur.u][k];
            const Edge &e = treeE[idx];
            int v = (e.a == cur.u) ? e.b : e.a;
            if (v == cur.parent) continue;
            if (v == PARK) return cur.eidx; // 树上路径唯一，碰到公园即收工
            Node nx;
            nx.u = v;
            nx.parent = cur.u;
            if (e.w > cur.wmx) { nx.wmx = e.w; nx.eidx = idx; }
            else { nx.wmx = cur.wmx; nx.eidx = cur.eidx; }
            stk.push_back(nx);
        }
    }
    return -1;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0; // 空输入安全返回
    nameId["Park"] = PARK;
    char s1[64], s2[64];
    int w;
    for (int i = 0; i < n; ++i) {
        if (scanf("%63s %63s %d", s1, s2, &w) != 3) break;
        int a = ident(string(s1)), b = ident(string(s2));
        if (a == PARK && b == PARK) continue; // 公园—公园的边没有意义
        Edge e;
        e.w = w;
        if (a == PARK || b == PARK) { // 人—公园边
            e.a = (a == PARK) ? b : a;
            e.b = PARK;
            linkE.push_back(e);
        } else { // 人—人边
            e.a = a;
            e.b = b;
            roadE.push_back(e);
        }
    }
    int s;
    if (scanf("%d", &s) != 1) s = 0;

    nodeCnt = nameId.size();
    for (int i = 0; i < nodeCnt; ++i) fa[i] = i;

    // 第一步：只用人—人边跑 Kruskal 得最小生成森林
    sort(roadE.begin(), roadE.end(), cmpEdge);
    for (int i = 0; i < (int)roadE.size(); ++i) {
        int ra = findRoot(roadE[i].a), rb = findRoot(roadE[i].b);
        if (ra != rb) {
            fa[ra] = rb;
            treeE.push_back(roadE[i]);
        }
    }

    // 每个连通块用最便宜的公园边接入公园，此时公园度数 = 连通块数 k
    for (int i = 0; i < (int)linkE.size(); ++i) {
        int root = findRoot(linkE[i].a);
        if (!hasCh[root]) {
            hasCh[root] = true;
            chW[root] = linkE[i].w;
            chV[root] = linkE[i].a;
            roots.push_back(root);
        } else if (linkE[i].w < chW[root]) {
            chW[root] = linkE[i].w;
            chV[root] = linkE[i].a;
        }
    }
    for (int i = 0; i < (int)roots.size(); ++i) {
        Edge e;
        e.w = chW[roots[i]];
        e.a = chV[roots[i]];
        e.b = PARK;
        treeE.push_back(e);
    }
    int k = roots.size();

    // 第二步：还有空车位时，反复做「加一条公园边、删路径上最重的非公园边」的交换
    for (int it = 0; it < s - k; ++it) {
        bool has = false;
        int bestGain = 0, bw = 0, bv = 0, bdrop = -1;
        for (int i = 0; i < (int)linkE.size(); ++i) {
            int drop = worstOnPath(linkE[i].a);
            if (drop < 0) continue; // 单人块没有内部边可删，加边只会翻倍停车
            int gain = linkE[i].w - treeE[drop].w;
            if (gain < 0 && (!has || gain < bestGain)) {
                has = true;
                bestGain = gain;
                bw = linkE[i].w;
                bv = linkE[i].a;
                bdrop = drop;
            }
        }
        if (!has) break; // 剩下的交换都会变贵，提前收手
        treeE.erase(treeE.begin() + bdrop);
        Edge e;
        e.w = bw;
        e.a = bv;
        e.b = PARK;
        treeE.push_back(e);
    }

    ll total = 0;
    for (int i = 0; i < (int)treeE.size(); ++i) total += treeE[i].w;
    printf("Total miles driven: %lld\n", total);
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 00:00
# update_at: 2026-10-02 00:00

import sys
from collections import defaultdict

PARK = 0  # 公园节点编号，人按出现顺序从 1 开始编号


def find(fa: list[int], x: int) -> int:
    """并查集查找（路径压缩），返回 x 所在连通块的根。"""
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x


def kruskal(edges: list[tuple[int, int, int]], m: int) -> tuple[list[tuple[int, int, int]], list[int]]:
    """只用人—人边跑最小生成森林，返回 (选中的边, 并查集)。"""
    fa = list(range(m))
    tree = []
    for w, a, b in sorted(edges):
        ra, rb = find(fa, a), find(fa, b)
        if ra != rb:
            fa[ra] = rb
            tree.append((w, a, b))
    return tree, fa


def worst_on_path(tree: list[tuple[int, int, int]], src: int) -> tuple[int, int, int] | None:
    """src 到公园的树上路径中，最重的「非公园边」；路径上没有（单点块）则 None。

    返回边本身而不是权值，调用方要把它从树上删掉。最后一段公园边不参与比较：
    删公园边不会让公园度数 +1，起不到「多停一辆车」的作用。
    """
    adj = defaultdict(list)
    for e in tree:
        w, a, b = e
        adj[a].append((b, w, e))
        adj[b].append((a, w, e))
    stack = [(src, PARK, -1, None)]  # (点, 来时的点, 路径最重非公园边权, 对应边)
    while stack:
        u, fa, w_mx, e_mx = stack.pop()
        for v, w, e in adj[u]:
            if v == fa:
                continue
            if v == PARK:  # 树上路径唯一，碰到公园即可收工
                return e_mx
            stack.append((v, u, max(w_mx, w), e if w > w_mx else e_mx))
    return None


def solve() -> None:
    it = iter(sys.stdin.read().split())
    n = int(next(it))

    name_id: dict[str, int] = {"Park": PARK}

    def ident(name: str) -> int:
        """名字 → 编号：公园固定为 PARK，其他人按出现顺序编号。"""
        if name not in name_id:
            name_id[name] = len(name_id)
        return name_id[name]

    road, link = [], []  # 人—人边 (w,a,b)；人—公园边 (w,人)
    for _ in range(n):
        a, b, w = ident(next(it)), ident(next(it)), int(next(it))
        if a == PARK and b == PARK:
            continue  # 公园—公园的边没有意义
        if a == PARK or b == PARK:
            link.append((w, b if a == PARK else a))
        else:
            road.append((w, a, b))

    s = int(next(it))
    tree, fa = kruskal(road, len(name_id))

    # 第一步：每个连通块用它最便宜的公园边接入公园，此时公园度数 = 连通块数 k
    cheapest: dict[int, tuple[int, int]] = {}  # 块根 -> (权, 人)
    for w, v in link:
        root = find(fa, v)
        if root not in cheapest or w < cheapest[root][0]:
            cheapest[root] = (w, v)
    for w, v in cheapest.values():
        tree.append((w, v, PARK))
    k = len(cheapest)

    # 第二步：还有空车位时，反复做「加一条公园边、删路径上最重的非公园边」的交换
    for _ in range(s - k):
        pick = None  # (净收益 w-删边权, 公园边权, 人, 要删的边)
        for w, v in link:
            drop = worst_on_path(tree, v)
            if drop is None:  # 单人块没有内部边可删，加边只会翻倍停车
                continue
            gain = w - drop[0]
            if gain < 0 and (pick is None or gain < pick[0]):
                pick = (gain, w, v, drop)
        if pick is None:  # 剩下的交换都会变贵，提前收手
            break
        _, w, v, drop = pick
        tree.remove(drop)
        tree.append((w, v, PARK))

    print(f"Total miles driven: {sum(w for w, _, _ in tree)}")


if __name__ == "__main__":
    solve()

复杂度

设人数为 $m\ (\leqslant 20)$ 、道路数为 $n$ 。Kruskal 排序占 $O(n \log n)$ ；每次交换要枚举每条公园边并各做一次 $O(m)$ 的树上路径扫描，交换至多进行 $m$ 次，总计 $O(n\log n + s\cdot m^2)$ 。对本题规模绰绰有余（实测全部 21 组测试数据约 0.02s、内存 15MB）。

总结

「车进公园即停 + 容量无限」把方案压缩成一棵包含 Park 的生成树，停车数就是 Park 的度数，本题即度限制最小生成树。
三段式解法：① 删掉 Park，对人—人边跑 Kruskal 得生成森林；② 每个连通块用最便宜的公园边接入，得到度数最小的最优树；③ 剩余车位用来反复做「加公园边、删路径最重非公园边」的最优交换，每次净收益 $w-w'<0$ 才执行。
交换的正确性依赖经典交换引理：度数为 $d$ 的最优树总能从度数为 $d-1$ 的最优树经一次最优交换得到。
实现细节：多重边交给排序；路径上只删非公园边；单人块没有可删边，跳过；没有负收益交换就提前结束（不要求停满）。

图示解析

一次「交换」长什么样

下图展示样例的第一次交换：加入 Herb-Park 24，删去路径 $Herb\to Eduardo\to Alphonzo\to Bernardo\to Park$ 上最重的非公园边 Eduardo-Herb 79。

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17交换前（度数 1，总里程 255）：      交换后（度数 2，总里程 200）：

        Park                            Park
         |                             /      \
     Bernardo                       19/        \24（加）
     /       \                        /          \
   32         82                 Bernardo        Herb
   /            \                 /       \        |
Alphonzo     Clemenzi          32         82      (79 已删)
   |             |              /           \
  43             |          Alphonzo     Clemenzi
   |             |             |
Eduardo ---------+            43
   |                           |
  79（删）                  Eduardo
   |                           |
 Herb                        Herb（改从 Park 直接进园）

观察重点：交换前 Herb 挂在树上，去公园要走 $79\to43\to32\to19$ ；加入 Herb-Park 24 后，环上 $Herb\to Eduardo\to Alphonzo\to Bernardo\to Park$ 中最重的非公园边是 $79$ ，删去它——总变化 $24-79=-55$ ，一次省下 55 公里；第二次交换（Clemenzi-Park 65 换 $82$ ， $\Delta=-17$ ）同理，省完 3 个车位刚好用完，答案 $183$ 。整个算法就是把这步「加公园边、删路径最重非公园边」重复到车位用完或不再变便宜为止。

目录