「一本通 3.1 练习 4」Tree

形式化题目

给定一个包含 $V$ 个顶点、 $E$ 条边的无向带权连通图，边分为两类：白色（标记为 0）和黑色（标记为 1）。要求从图中选出一个生成树，满足：

树中包含的白色边数恰好为 $\text{need}$ ；
树上所有边的权值和最小。

保证图中至少存在一棵满足要求的生成树。

正解

思路

1. 朴素瓶颈与凸性观察

直接寻找“恰好包含 $\text{need}$ 条白色边”的最小生成树是一个带基数约束的组合优化问题。如果单纯枚举白边的选取组合，或者记录选入白边数的动态规划，状态维度过大，在 $V \le 5\times 10^4, E \le 10^5$ 的规模下无法求解。

设函数 $f(k)$ 表示恰好选取 $k$ 条白边时的最小生成树最小权值和。由图拟阵交的性质与拟阵交凸优化理论可知：当我们在生成树中每多强制增加一条白边时，替换所产生的边权代价增量是非减的。也就是说，离散函数 $f(k)$ 关于白边数量 $k$ 构成一个下凸函数（凸包的斜率单调递增）。

2. WQS 二分（带权二分）转化

既然点集 $(k, f(k))$ 是下凸的，我们可以用一条斜率为 $-x$ 的直线从下方去切该凸包：

\min_k \{ f(k) + k \cdot x \}

在现实意义中，给所有的白色边权值统一加上一个附加权值 $x$ （偏移量 bonus）：

当 $x > 0$ 时，白边变贵，算法在选边时会减少白边的数量；
当 $x < 0$ 时，白边变便宜，算法在选边时会增加白边的数量。

对于任意固定的附加权值 $x$ ，给白边加上 $x$ 后的全局无约束最小生成树（直接运行标准 Kruskal），其选出的白边数量即为该切线在凸包上的切点横坐标，所得的权值和恰好等于截距 $f(k) + k \cdot x$ 。

因此，我们可以对白边的额外权值 $x$ 进行二分：

如果运行 Kruskal 选出的白边数量 $cnt \ge \text{need}$ ，说明当前白边仍然偏多（或刚好达标），白边还可以更贵一些，我们记录当前偏移量 $x$ ，并向右半区间 $[mid + 1, high]$ 继续二分；
如果选出的白边数量 $cnt < \text{need}$ ，说明白边太贵了导致选少了，应向左半区间 $[low, mid - 1]$ 缩小偏移量。

graph LR
    subgraph WQS 二分过程
        A["二分白边偏移量 bonus"] --> B["白边权值统一加 bonus"]
        B --> C["Kruskal 跑无约束最小生成树"]
        C --> D{"白边数量 cnt 与 need 比较"}
        D -- "cnt >= need" --> E["记录候选 bonus，尝试增大 bonus"]
        D -- "cnt < need" --> F["减小 bonus 使得白边更优先"]
    end

3. 共线处理与答案还原

在实际计算中，可能存在多个点在凸包上共线（即存在某个斜率 $-x$ ，在此斜率下选不同数量白边的最小生成树权值完全相同）。此时可能恰好存在 $k = \text{need}$ 落在共线线段中间的情况。

为了保证二分收敛与截距正确：

我们在 Kruskal 排序/选边策略中约定：当黑边与加权后的白边权值相同时，优先选取白边。
这样，在共线段上我们总会贪心选取最右侧的端点（即白边数最大），保证只要线段覆盖了 $\text{need}$ ，就能判定出 $cnt \ge \text{need}$ 。
关键在于：共线段上所有点在切线下的截距都是相同的常数 $C = f(k) + k \cdot x$ 。因此，哪怕最终生成树选取的白边数 $k_{\max} > \text{need}$ ，原问题的答案依然可以直接通过截距还原：
$f(\text{need}) = \text{总权值} - \text{need} \cdot x$

4. 双指针归并优化

如果在每次二分判定中都对所有 $E$ 条边重新进行快速排序，单次复杂度为 $O(E \log E)$ 。注意到白边之间、黑边之间的相对大小关系在给白边加上常数 $x$ 后均不会改变。因此，我们预先对白边列表和黑边列表分别排序一次；二分时，利用双指针以 $O(E)$ 的线性时间将两组有序边归并，结合并查集即可在极短时间内完成单次 Kruskal 检验。

代码

Python 版：

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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

# 边信息类型：(u, v, weight)
Edge = tuple[int, int, int]


def kruskal(n: int, whites: list[Edge], blacks: list[Edge], bonus: int) -> tuple[int, int]:
    """计算给白边增加 bonus 权值后的最小生成树白边数与总权值。

    同权时优先选白边，便于二分出满足 need 条白边的最小额外偏移。
    """
    parent = list(range(n))

    def find(x: int) -> int:
        curr = x
        while parent[curr] != curr:
            curr = parent[curr]
        while x != curr:
            parent[x], x = curr, parent[x]
        return curr

    # 双指针归并白边（带 bonus）与黑边，因两组各自有序，归并只需 O(E)
    total_weight = white_cnt = chosen = 0
    w_idx = b_idx = 0
    w_len, b_len = len(whites), len(blacks)

    while chosen < n - 1 and (w_idx < w_len or b_idx < b_len):
        take_white = (
            b_idx >= b_len
            or (
                w_idx < w_len
                and whites[w_idx][2] + bonus <= blacks[b_idx][2]  # 权值相同时白边优先
            )
        )

        u, v, w, is_white = (
            (whites[w_idx][0], whites[w_idx][1], whites[w_idx][2] + bonus, 1)
            if take_white
            else (blacks[b_idx][0], blacks[b_idx][1], blacks[b_idx][2], 0)
        )
        if take_white:
            w_idx += 1
        else:
            b_idx += 1

        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total_weight += w
            white_cnt += is_white
            chosen += 1

    return white_cnt, total_weight


def solve() -> None:
    raw = sys.stdin.buffer.read().split()
    if not raw:
        return
    data = iter(raw)
    n, m, need = int(next(data)), int(next(data)), int(next(data))

    whites: list[Edge] = []
    blacks: list[Edge] = []
    for _ in range(m):
        u, v, c, col = int(next(data)), int(next(data)), int(next(data)), int(next(data))
        if col == 0:
            whites.append((u, v, c))
        else:
            blacks.append((u, v, c))

    whites.sort(key=lambda e: e[2])
    blacks.sort(key=lambda e: e[2])

    # WQS 二分 / 带权二分：二分白边额外权值 bonus ∈ [-105, 105]
    low, high = -105, 105
    best_bonus = 0
    while low <= high:
        mid = (low + high) // 2
        cnt, _ = kruskal(n, whites, blacks, mid)
        if cnt >= need:  # 白边选多了或恰好，说明 bonus 还可以更大（惩罚不够或恰好）
            best_bonus = mid
            low = mid + 1
        else:
            high = mid - 1

    _, total = kruskal(n, whites, blacks, best_bonus)
    # 真实最优生成树权值和 = 调整后的生成树权值和 - need * best_bonus
    ans = total - need * best_bonus
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 04:11
 * update_at: 2026-10-05 04:11
 */
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MAXE = 100005; // 边数上限
const int MAXN = 50005;  // 点数上限

struct Edge {
    int u;
    int v;
    int w;
};

int n, m;
ll need; // 生成树中必须包含的白边条数

Edge whites[MAXE]; // 白边列表，按边权升序
Edge blacks[MAXE]; // 黑边列表，按边权升序
int white_num;     // 白边条数
int black_num;     // 黑边条数

int fa[MAXN]; // 并查集父节点

// 边按权值升序，用于提前把白边、黑边各自排好序
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// 并查集查找，带路径压缩
int find_root(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

// 给每条白边额外附加权值 bonus 后跑一次无约束 Kruskal。
// 白边、黑边两组已各自有序，用双指针归并成整体有序，单次只需 O(E)。
// 返回选入的白边条数，adjusted_weight 带回调整后的生成树总权值。
int kruskal(ll bonus, ll &adjusted_weight) {
    for (int i = 0; i < n; i++) {
        fa[i] = i;
    }
    int chosen = 0;     // 已选入生成树的边数
    int white_used = 0; // 已选入的白边条数
    ll total = 0;       // 调整后的生成树总权值
    int wi = 0;         // 白边指针
    int bi = 0;         // 黑边指针

    while (chosen < n - 1 && (wi < white_num || bi < black_num)) {
        // 白边用尽时只能取黑边；白边权值不超过黑边时取白边
        // 权值相同时固定优先取白边，保证二分的单调性
        bool take_white = true;
        if (wi >= white_num) {
            take_white = false;
        } else if (bi < black_num && blacks[bi].w < whites[wi].w + bonus) {
            take_white = false;
        }

        int u, v;
        ll w;
        if (take_white) {
            u = whites[wi].u;
            v = whites[wi].v;
            w = whites[wi].w + bonus;
            wi++;
        } else {
            u = blacks[bi].u;
            v = blacks[bi].v;
            w = blacks[bi].w;
            bi++;
        }

        int ru = find_root(u);
        int rv = find_root(v);
        if (ru == rv) {
            continue; // 两端已连通，这条边舍弃
        }
        fa[ru] = rv;
        total += w;
        chosen++;
        if (take_white) {
            white_used++;
        }
    }

    adjusted_weight = total;
    return white_used;
}

int main() {
    scanf("%d %d %lld", &n, &m, &need);

    white_num = 0;
    black_num = 0;
    for (int i = 0; i < m; i++) {
        int s, t, c, col;
        scanf("%d %d %d %d", &s, &t, &c, &col);
        if (col == 0) {
            whites[white_num].u = s;
            whites[white_num].v = t;
            whites[white_num].w = c;
            white_num++;
        } else {
            blacks[black_num].u = s;
            blacks[black_num].v = t;
            blacks[black_num].w = c;
            black_num++;
        }
    }

    // 白边权值只比黑边大/小有限范围，一次排序后二分内部无需再排序
    sort(whites, whites + white_num, cmp_edge);
    sort(blacks, blacks + black_num, cmp_edge);

    // WQS 二分：找“选出的白边条数 >= need”的最大附加权值 best_bonus
    int low = -105;
    int high = 105;
    int best_bonus = 0;
    ll dummy = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int cnt = kruskal(mid, dummy);
        if (cnt >= need) {
            best_bonus = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // 用 best_bonus 再跑一次，截距还原出恰好 need 条白边的最小权值和
    ll adjusted = 0;
    kruskal(best_bonus, adjusted);
    ll ans = adjusted - need * best_bonus;
    printf("%lld\n", ans);

    return 0;
}

复杂度

时间复杂度：
- 预处理对白边和黑边各自排序： $O(E_w \log E_w + E_b \log E_b) = O(E \log E)$ ；
- 二分区间长度为 $[-105, 105]$ ，总迭代次数约为 $\approx 8$ 次；
- 每次迭代双指针扫描归并 $O(E)$ ，并查集操作 $O(E \alpha(V))$ ；
- 整体时间复杂度为 $O(E \log E + 8 \cdot E \alpha(V))$ ，运行极为迅速。
空间复杂度：
- 存储白边与黑边列表需 $O(E)$ 空间；
- 并查集父节点数组需 $O(V)$ 空间；
- 整体空间复杂度为 $O(V + E)$ 。

总结

本题是 WQS 二分 / 带权二分（Aliens Trick） 的典中典。它将带数量限制的图论优化问题转化为无约束的最优化问题，其本质利用了目标函数关于限制参数的凸性，通过二分拉格朗日乘子（斜率）完成降维求解。同时，预先分流排序配合二分内部线性双指针归并，大幅降低了时间常数。