[APIO2008] 免费道路

GitHub跳转原题关系图返回列表

两遍 Kruskal：第一遍先加水泥路求鹅卵石路下界 need 并标记被迫边，第二遍放回被迫边、补鹅卵石路到 k 条、水泥路填满，得恰好含 k 条免费路的生成树。

OJ: luogu

题目 ID: P3623

难度:普及+/提高-

标签:最小生成树并查集Kruskal图论构造

创建: 2026-10-22 12:18

更新: 2026-10-21 00:00

形式化题目

给定 $N$ 个点、 $M$ 条边的无向图，每条边带类型 $c \in \{0, 1\}$ （ $0$ = 鹅卵石路， $1$ = 水泥路），再给整数 $K$ 。要求选出 $N-1$ 条边构成生成树，且其中类型为 $0$ 的边恰好 $K$ 条；输出任一合法方案，无解输出 no solution。 $1 \le N \le 2 \times 10^4$ ， $1 \le M \le 10^5$ ， $0 \le K \le N-1$ ，无重边。

这是一个带数量约束的生成树问题：不是求权和最小，而是要求生成树里某一类边的条数精确等于 $K$ 。答案不唯一，任意合法方案均可。

暴力解法

思路

最直接的做法：枚举 $M$ 条边各自的"选 / 不选"，到叶子统一检查完整方案——恰好 $N-1$ 条、整图连通、鹅卵石路恰好 $K$ 条。这就是 dfs(dep) 决定第 dep 条边、check() 在叶子统一验证的 01 序列套路。

代码

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/**
 * 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-21 00:00
 * update_at: 2026-10-21 00:00
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 01 序列枚举每条道路"免费 / 收费"：dfs(dep) 决定第 dep 条道路选不选，
// 到叶子统一检查三件事：恰好 n-1 条、整图连通、鹅卵石路恰好 k 条。
// 复杂度 O(2^m * (n+m))，只适合 m <= 20 左右的小数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;   // 小数据村庄数上限
const int MAXM = 25;   // 小数据道路数上限

int n, m, k;
int eu[MAXM];      // eu[i]：第 i 条道路的端点 u
int ev[MAXM];      // ev[i]：第 i 条道路的端点 v
int ec[MAXM];      // ec[i]：第 i 条道路类型，0 鹅卵石 1 水泥
int choose_[MAXM]; // choose_[i]：第 i 条道路选(1)/不选(0)
int parent[MAXN];  // check 里用的并查集

// 小工具：并查集找根（路径压缩）
int find_root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find_root(parent[x]);
}

// 检查一个完整的选边方案：n-1 条、连通、鹅卵石路恰 k 条。
bool check() {
    int total = 0, cobble = 0;
    for (int i = 1; i <= m; i++)
        if (choose_[i]) {
            total++;
            if (ec[i] == 0) cobble++;
        }
    if (total != n - 1 || cobble != k) return false;  // 不是生成树或鹅卵石数不对

    for (int i = 1; i <= n; i++) parent[i] = i;
    for (int i = 1; i <= m; i++)
        if (choose_[i]) {
            int ru = find_root(eu[i]);
            int rv = find_root(ev[i]);
            if (ru != rv) parent[ru] = rv;  // 合并；若有环 total 已不对，无需再查
        }
    // n-1 条边 + 无环 等价于 生成树；这里直接数连通块兜底
    int blocks = 0;
    for (int i = 1; i <= n; i++)
        if (find_root(i) == i) blocks++;
    return blocks == 1;
}

// 01 序列递归：这一层在决定第 dep 条道路选不选。
bool dfs(int dep) {
    if (dep > m) return check();  // 完整方案已生成，统一检查
    choose_[dep] = 0;             // 不选第 dep 条
    if (dfs(dep + 1)) return true;
    choose_[dep] = 1;             // 选第 dep 条
    return dfs(dep + 1);
}

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

    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) cin >> eu[i] >> ev[i] >> ec[i];

    if (!dfs(1))
        cout << "no solution" << "\n";
    else {
        for (int i = 1; i <= m; i++)
            if (choose_[i]) cout << eu[i] << " " << ev[i] << " " << ec[i] << "\n";
    }
    return 0;
}

复杂度

$O(2^M \cdot (N + M))$ 。 $M = 20$ 时约 $10^6 \cdot$ 检查开销，勉强能跑； $M = 10^5$ 时完全不可行。

瓶颈

生成树的数量是指数级的，逐个枚举无法覆盖真实规模。问题出在"选哪 $N-1$ 条边"被当成自由组合来搜，而没有利用结构：生成树判定天然适合 Kruskal 的"按序试边 + 并查集"，且"恰好 $K$ 条 0 类边"可以拆成"至少 $K$ 条"和"至多 $K$ 条"两个单侧界分别求。

正解

思路

第一步：求鹅卵石路数的下界 need

第一遍 Kruskal：先加全部水泥路，能用则用；然后剩下的连通块之间已经没有水泥路可走（否则早就合并了），只能靠鹅卵石路桥接。补进来的桥接边条数记为 need，并且把每条这样的鹅卵石路标记为被迫边（forced）。

为什么这给出了真正的下界？把水泥连通块各自收缩成一个点，收缩图是连通的（否则整个图不连通），且它的每条边都对应原图的一条鹅卵石路。任何生成树在收缩图上的像也是生成树，必须横跨所有块间连接——而这些连接全是鹅卵石路，所以任何生成树都至少含 need 条鹅卵石路。同时这也说明：

图不连通（水泥边数 + need ≠ N-1）⇒ 无解；
need > K ⇒ 无解（下界已经超过要求）。

反过来，need ≤ K 时并不是直接有解——还要看上界。

第二步：从下界出发，恰好凑到 K 条

第二遍 Kruskal 分三段：

放回被迫边：forced 集（need 条）本身是森林——第一遍里每一条都真正合并了两个不同集合——所以重新放回必然全部成功；
凑鹅卵石路：从其余鹅卵石路里，按输入顺序挑"能继续扩大森林"的边，直到凑满 $K$ 条；
水泥路填满：用水泥路把森林补成一棵完整的生成树。

关键在两处：

凑不满 $K$ 条 ⇒ 无解。第 2 段是"只把鹅卵石路当可用边做 Kruskal"，它能选入的最大条数 cap 就是所有生成树中鹅卵石路边数的上界：任何生成树的鹅卵石边子集自身是森林，而只考虑鹅卵石路的 Kruskal 得到的就是鹅卵石路森林的最大边数。cap < K ⇒ 任何生成树都放不下 $K$ 条鹅卵石路。
水泥路一定能填满，且总数恰好 $N-1$ 。第一遍那棵生成树 $T_1$ 由 水泥边 + forced 鹅卵石边 组成；第二遍已选的 $K$ 条鹅卵石路 $S \supseteq \text{forced}$ ，于是 $T_1 \setminus S$ 全部是水泥边。第 3 段对全部水泥边做 Kruskal， $T_1 \setminus S$ 里的每条水泥边要么被选入、要么因两端已被 $S$ 中更早的鹅卵石路连通而成为环边（此时 $S \cup$ 已选水泥边已覆盖了它的连接作用）。两种情况最终都连通，且因为生成树只有 $N-1$ 条边，水泥阶段恰好补进 $N-1-K$ 条，鹅卵石路恰好 $K$ 条。

为什么第二遍必须先放回被迫边

如果跳过被迫边、直接贪心选鹅卵石路的前缀，选中的鹅卵石边可能把水泥路"堵死"：某条鹅卵石边连接了两个本可由水泥路连通的块，占掉树上的位置后，可能没有足够的水泥边去连接真正必须用鹅卵石路连接的块。先放回被迫边，就锁定了"必须用鹅卵石路"的连接，剩下的 $K - \text{need}$ 条在自由位置上挑选，水泥路只需填满非被迫位置——由上面的论证，这总能做到。

样例推演

官方样例（ $N=5, M=7, K=2$ ），第一遍先加水泥路 $(4,5)$ 、 $(5,3)$ 、 $(1,2)$ （边 2、4、6）， $(4,2)$ 成环；连通块为 $\{1,2,3,4,5\}$ 之外的…… 实际上水泥路已把 $\{1,2\},\{3,4,5\}$ 合成两块，鹅卵石路 $(1,3)$ 桥接，need = 1，边 1 被标记 forced。第二遍放回边 1，再选鹅卵石路 $(3,2)$ （凑到 $K=2$ ），水泥路 $(4,5),(5,3),(1,2)$ 补满，得到 4 条边的生成树，恰含 2 条鹅卵石路。三个程序（main.cpp、main.py、brute.cpp）输出的是三种不同但都合法的方案——这正是本题答案不唯一的体现。

代码

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/**
 * 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-21 00:00
 * update_at: 2026-10-21 00:00
 */
// P3623 [APIO2008] 免费道路：两遍 Kruskal 构造一棵恰好含 k 条鹅卵石路的生成树。
#include <bits/stdc++.h>
using namespace std;

// 一条无向道路：连接村庄 u、v；c = 0 是鹅卵石路（免费），c = 1 是水泥路。
struct Edge {
    int u;
    int v;
    int c;
};

const int MAXN = 2e4 + 5;  // 村庄数上限
const int MAXM = 1e5 + 5;  // 道路数上限

int n, m, k;
Edge edges[MAXM];  // edges[i]：第 i 条道路，编号与输入一致（1..m）

// 并查集：路径压缩 + 按大小合并，风格对齐 rbook 的 Kruskal 模板。
int dsu_parent[MAXN];  // dsu_parent[x]：x 的父节点，x 是根时等于 x
int dsu_size[MAXN];    // dsu_size[x]：x 当根时所在集合的大小

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合；两端本来就连通（这条边成环）时返回 false。
bool dsu_merge(int a, int b) {
    int root_a = dsu_find(a);
    int root_b = dsu_find(b);
    if (root_a == root_b) return false;
    // 小集合接到大集合下面，配合路径压缩，单次操作接近常数。
    if (dsu_size[root_a] < dsu_size[root_b]) swap(root_a, root_b);
    dsu_parent[root_b] = root_a;
    dsu_size[root_a] += dsu_size[root_b];
    return true;
}

void dsu_reset() {
    for (int i = 1; i <= n; i++) {
        dsu_parent[i] = i;
        dsu_size[i] = 1;
    }
}

bool forced[MAXM];  // forced[i]：第一遍里"不得不选"的鹅卵石路（桥接水泥连通块）
int plan[MAXM];     // 最终方案的边编号
int plan_cnt;       // 方案里的边数，一棵生成树正好 n - 1 条

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

    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) cin >> edges[i].u >> edges[i].v >> edges[i].c;

    // ---------- 第一遍 Kruskal：先加全部水泥路，再补鹅卵石路 ----------
    // 目的：求出"任何生成树都至少需要"的鹅卵石路条数 need。
    // 只用水泥路先连通能连通的局部，剩下的连通块之间没有水泥路可走，
    // 只能靠鹅卵石路桥接，所以这一遍补进来的鹅卵石路条数就是下界 need。
    dsu_reset();
    int cement_cnt = 0;  // 第一遍选中的水泥路条数
    for (int i = 1; i <= m; i++)
        if (edges[i].c == 1 && dsu_merge(edges[i].u, edges[i].v)) cement_cnt++;
    int need = 0;  // 任何生成树至少要用的鹅卵石路条数
    for (int i = 1; i <= m; i++)
        if (edges[i].c == 0 && dsu_merge(edges[i].u, edges[i].v)) {
            forced[i] = true;  // 桥接水泥连通块，"不得不选"
            need++;
        }

    // 图本身不连通（拼不成 n-1 条），或者最少的鹅卵石路都超过 k，都无解。
    if (cement_cnt + need != n - 1 || need > k) {
        cout << "no solution" << "\n";
        return 0;
    }

    // ---------- 第二遍 Kruskal：精确凑够 k 条鹅卵石路 ----------
    // 先放回第一遍"不得不选"的鹅卵石路（need 条）；
    // 再从其余鹅卵石路里挑还能扩大森林的边，直到凑满 k 条；
    // 最后用水泥路补满生成树。
    dsu_reset();
    plan_cnt = 0;
    int cobble_cnt = 0;  // 方案里已有的鹅卵石路条数
    for (int i = 1; i <= m; i++)
        if (forced[i]) {
            dsu_merge(edges[i].u, edges[i].v);  // forced 是森林，必定合并成功
            plan[++plan_cnt] = i;
            cobble_cnt++;
        }
    for (int i = 1; i <= m && cobble_cnt < k; i++)
        if (edges[i].c == 0 && !forced[i] && dsu_merge(edges[i].u, edges[i].v)) {
            plan[++plan_cnt] = i;
            cobble_cnt++;
        }
    if (cobble_cnt < k) {  // 凑不满 k 条：k 超过鹅卵石路在生成树里的上限
        cout << "no solution" << "\n";
        return 0;
    }
    // 水泥路补满：forced 集合 + 全部水泥路已经包含第一遍的那棵生成树，
    // 所以这一步结束后一定连通，恰好再补进 n-1-k 条水泥路。
    for (int i = 1; i <= m; i++)
        if (edges[i].c == 1 && dsu_merge(edges[i].u, edges[i].v)) plan[++plan_cnt] = i;

    sort(plan + 1, plan + plan_cnt + 1);  // 按输入顺序输出，便于对照
    for (int j = 1; j <= plan_cnt; j++) {
        Edge &e = edges[plan[j]];
        cout << e.u << " " << e.v << " " << e.c << "\n";
    }
    return 0;
}

Python 版与 C++ 逐阶段对应：Dsu 类封装 find/merge，第一遍求 need 并标记 forced，第二遍三段式凑方案。

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#!/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-21 00:00
# update_at: 2026-10-21 00:00

import sys


class Dsu:
    """并查集：路径压缩 + 按大小合并，对应 C++ 版的 dsu_find / dsu_merge。"""

    def __init__(self, n: int) -> None:
        self.parent = list(range(n + 1))  # parent[x]：x 的父节点，x 是根时等于 x
        self.size = [1] * (n + 1)         # size[x]：x 当根时所在集合的大小

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 路径减半
            x = self.parent[x]
        return x

    def merge(self, a: int, b: int) -> bool:
        """合并 a、b 所在集合；两端已连通（这条边成环）返回 False。"""
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False
        if self.size[root_a] < self.size[root_b]:  # 小的接到大的下面
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, k = next(data), next(data), next(data)

    # edges[i]：第 i 条道路 (u, v)，c = 0 鹅卵石路，c = 1 水泥路
    edges = [(next(data), next(data), next(data)) for _ in range(m)]

    # ---------- 第一遍 Kruskal：先加全部水泥路，再补鹅卵石路 ----------
    # 求出"任何生成树至少需要"的鹅卵石路条数 need，
    # 同时标记桥接水泥连通块的"不得不选"鹅卵石路 forced。
    dsu = Dsu(n)
    cement_cnt = sum(dsu.merge(u, v) for u, v, c in edges if c == 1)
    forced = [False] * (m + 1)
    need = 0
    for i, (u, v, c) in enumerate(edges, 1):
        if c == 0 and dsu.merge(u, v):
            forced[i] = True
            need += 1

    # 图不连通，或最少的鹅卵石路都超过 k，都无解。
    if cement_cnt + need != n - 1 or need > k:
        print("no solution")
        return

    # ---------- 第二遍 Kruskal：精确凑够 k 条鹅卵石路 ----------
    # 先放回 forced 的鹅卵石路，再挑其余鹅卵石路补到 k 条，最后水泥路填满。
    dsu = Dsu(n)
    plan: list[int] = []  # 方案的边编号，恰好 n - 1 条
    for i, (u, v, c) in enumerate(edges, 1):
        if forced[i]:
            dsu.merge(u, v)  # forced 是森林，必定合并成功
            plan.append(i)
    cobble_cnt = len(plan)
    for i, (u, v, c) in enumerate(edges, 1):
        if cobble_cnt >= k:
            break
        if c == 0 and not forced[i] and dsu.merge(u, v):
            plan.append(i)
            cobble_cnt += 1
    if cobble_cnt < k:  # 凑不满 k 条：鹅卵石路在生成树里放不下这么多
        print("no solution")
        return
    for i, (u, v, c) in enumerate(edges, 1):
        if c == 1 and dsu.merge(u, v):
            plan.append(i)

    plan.sort()  # 按输入顺序输出，便于对照
    out = [f"{edges[i - 1][0]} {edges[i - 1][1]} {edges[i - 1][2]}" for i in plan]
    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

两遍 Kruskal 共 $O(M \cdot \alpha(N))$ （DSU 路径压缩 + 按大小合并， $\alpha$ 近似常数），输出前排序 $O(N \log N)$ ，总时间 $O(M \alpha(N) + N \log N)$ ，空间 $O(N + M)$ 。本题 $N \le 2 \times 10^4$ 、 $M \le 10^5$ ，实测 C++ 0.04s、Python 0.23s（ $N = 2 \times 10^4$ 、 $M = 10^5$ 、 $K = 9000$ 的随机连通图）。

总结

本题是"带数量约束的生成树"：不排序、不求权值和，只要求某类边恰好 $K$ 条。解法是把双向约束拆开——下界用"先水泥后鹅卵石"的 Kruskal 求出 need，上界用"被迫边 + 鹅卵石路贪心扩森林"验证 cap。
无解当且仅当三个条件之一：图不连通、need > K、cap < K。每个条件都独立蕴含"不存在满足要求的生成树"，合起来给出完整的判定。
第二遍先放回被迫边是正确性的核心：它锁定必须用鹅卵石路的连接，剩余位置自由分配，水泥路必然能填满。
实现上两遍都是普通 Kruskal 变体，DSU 完全复用；brute.cpp 的 01 序列枚举只服务小数据对拍与题意理解。

验证记录

官方样例 in1：main.cpp、main.py、brute.cpp 均通过独立校验（边存在、 $N-1$ 条、连通、鹅卵石恰 $K=2$ 条）。
对拍：gen.py 生成 320 组小图（ $1 \le N \le 7$ ，0/1 混合边， $0 \le K \le N-1$ ，其中有解 116 组、无解 204 组，无解占 63.8%），main.cpp 与 main.py 的输出全部通过独立合法性校验器，有解/无解判定与 brute.cpp 100% 一致（320/320）。
规模测试： $N = 2 \times 10^4$ 、 $M = 10^5$ 、 $K = 9000$ 的随机连通图，C++ 0.037s / Python 0.229s，输出均为恰含 9000 条鹅卵石路的生成树。

P3623 [APIO2008] 免费道路

题目描述

新亚（New Asia）王国有 $N$ 个村庄，由 $M$ 条道路连接。其中一些道路是鹅卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。

国王已决定保持尽可能少的道路免费，但是两个不同的村庄之间都应该有且仅有一条均由免费道路组成的路径连接。同时，虽然水泥路更适合现代交通的需要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好 $K$ 条鹅卵石路免费。

举例来说，假定新亚王国的村庄和道路如图 3(a) 所示。如果国王希望保持两条鹅卵石路免费，那么可以如图 3(b) 中那样保持道路 $(1, 2)$ ， $(2, 3)$ ， $(3, 4)$ 和 $(3, 5)$ 免费。该方案满足了国王的要求，因为：

两个村庄之间都有一条由免费道路组成的路径。
免费的道路已尽可能少。
方案中刚好有两条鹅卵石道路 $(2, 3)$ 和 $(3, 4)$ 。

图 3：(a) 新亚王国中村庄和道路的一个示例。实线标注的是水泥路，虚线标注的是鹅卵石路。(b) 一个保持两条鹅卵石路免费的维护方案。图中仅标出了免费道路。

给定一个关于新亚王国村庄和道路的数目以及国王决定保持免费的鹅卵石道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果存在则任意输出一个方案。

输入格式

输入第一行包含三个由空格隔开的整数：

$N$ ，村庄的数目 $(1 \le N \le 2 \times 10^4)$ ；

$M$ ，道路的数目 $(1 \le M \le 10^5)$ ；

$K$ ，国王希望保持免费的鹅卵石道路数目 $(0 \le K \le N - 1)$ 。

此后 $M$ 行述了新亚王国的道路，编号分别为 $1$ 到 $M$ 。第 $(i+1)$ 行述了第 $i$ 条道路的情况。用 3 个由空格隔开的整数述：

$u_i$ 和 $v_i$ ，为第 $i$ 条道路连接的两个村庄的编号，村庄编号为 $1$ 到 $N$ ；

$c_i$ ，表示第 $i$ 条道路的类型。 $c_i = 0$ 表示第 $i$ 条道路是鹅卵石路， $c_i = 1$ 表示第 $i$ 条道路是水泥路。

输入数据保证一对村庄之间至多有一条道路连接。

输出格式

如果满足国王要求的道路维护方案不存在，你的程序应该在输出第一行打印 no solution。否则，你的程序应该输出一个符合要求的道路维护方案，也就是保持免费的道路列表。按照输入中给定的那样输出免费的道路。如果有多种合法方案，你可以任意输出一种。

输入输出样例 #1

输入 #1

text

输出 #1