网络连接

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

利用边只跨越至多 6 个编号的限制，维护窗口连通分量做 Steiner Tree 前沿 DP。

OJ: shumeng

题目 ID: CSP201604E

难度:提高+/省选-

标签:状态压缩连通性DP轮廓DP图论Steiner Tree

日期: 2026-07-31 16:21

形式化题目

给定 $n$ 个设备的带权无向图，其中可以建立的连线 $(u, v)$ 一定满足 $|u - v| \le p$ 。若干设备是用户设备。可以选择任意设备作中继并挑选若干连线，要求所有用户设备互相连通，求所选边权和的最小值。

思路

小数据可以直接枚举每条边是否选择，然后用并查集检查所有用户设备是否在同一集合中。

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:48
 */
// brute.cpp：小数据暴力解，递归枚举每条边选或不选。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const int MAXM = 3005;
const long long INF = (1LL << 60);

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

int n, m, p;
int is_user[MAXN];
int choose_edge[MAXM];
Edge edges[MAXM];
int parent[MAXN];
long long answer;

int find_root(int x) {
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

bool check_connected() {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        if (!choose_edge[i]) {
            continue;
        }
        int x = find_root(edges[i].u);
        int y = find_root(edges[i].v);
        if (x != y) {
            parent[x] = y;
        }
    }

    int root = 0;
    for (int i = 1; i <= n; i++) {
        if (!is_user[i]) {
            continue;
        }
        if (root == 0) {
            root = find_root(i);
        } else if (root != find_root(i)) {
            return false;
        }
    }
    return true;
}

void dfs(int index, long long cost) {
    if (cost >= answer) {
        return;
    }
    if (index > m) {
        if (check_connected()) {
            answer = cost;
        }
        return;
    }

    choose_edge[index] = 0;
    dfs(index + 1, cost);
    choose_edge[index] = 1;
    dfs(index + 1, cost + edges[index].w);
}

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

    int test_count;
    cin >> test_count;
    while (test_count--) {
        cin >> n >> m >> p;
        string users;
        cin >> users;
        for (int i = 1; i <= n; i++) {
            is_user[i] = users[i - 1] == '1';
        }
        for (int i = 1; i <= m; i++) {
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
        }

        answer = INF;
        dfs(1, 0);
        cout << answer << '\n';
    }

    return 0;
}

这有 $2^m$ 种选择，无法处理正式数据。关键是按设备编号从小到大扫描时，处理到设备 $i$ 后，编号小于 $i-p$ 的设备不可能再与未来设备相连。因此，未来真正能接触到的只有最近 $p$ 个设备。

窗口状态设计

令插入设备 $i$ 前的窗口为 $i-p, i-p+1, \ldots, i-1$ ，编号不在 $1 \sim n$ 内的位置视为空。一个 DP 状态记录：

窗口每个位置是 0（该设备不选）或一个连通分量标签；相同标签表示已经连通。
每个连通分量额外记录它是否含有已处理的用户设备。
状态值是已选择边的最小费用。标签按从左到右第一次出现的顺序重新编号，使同一个划分只有一个编码。

插入与枚举连接

插入 $i$ 时，用户设备必须选入，普通设备还可以直接不选。选入时先把它作为新分量；对于每个能与它连边的旧分量，只保留其中最便宜的一条边，再枚举连接哪些旧分量。

这是充分的：任意可行解都可删去环变成森林；若新设备与同一个旧分量连了两次，也会产生环。边权非负，删去多余边不会变差。

样例窗口转移

下表展示官方样例处理设备 6 时的一轮前沿 DP。设备 1 和 3 已由边 1-3（费用 100）连成一个含用户的分量，0 表示空槽或未选设备。

阶段	窗口设备	分量标签	本轮选择	累加费用
插入 `6` 前	`0,1,2,3,4,5`	`0,1,0,1,0,0`	已有分量 `1={1,3}`	-
插入 `6`	`0,1,2,3,4,5,6`	`0,1,0,1,0,0,1`	选 `3-6`，费用 100	`+100`
忘记最左空槽后	`1,2,3,4,5,6`	`1,0,1,0,0,1`	分量仍在窗口内	不变

设备 6 还可以连边 1-6，但它和 3-6 指向同一旧分量，费用更高。DP 对该分量只保留 3-6，正好对应上面的删环结论。

离开窗口的判断

每次插入后忘记窗口最左设备：若它所在分量还留有其他窗口设备，继续保留；若整个分量不含用户，可以丢弃；若含用户却完全离开窗口，则它永远不能再与未来连边。这样的状态只有在没有未来用户、也没有其他含用户分量时才是一个完整答案，其余情况全部无效。

扫描完 $n$ 后，再插入 $p$ 个虚拟的空设备，以相同规则清空窗口并触发最终答案检查。

代码

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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:48
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const int MAXP = 6;
const int STATE_BITS = 24;
const int STATE_COUNT = 1 << STATE_BITS;
const long long INF = (1LL << 60);

struct StateCost {
    int code;
    long long value;
};

int n, m, p;
int is_user[MAXN];
int suffix_user[MAXN + 2];
long long edge_cost[MAXN][MAXP + 1];
long long *best;
long long answer;
vector<StateCost> current_states;
vector<int> next_codes;

// 把窗口内的连通分量重新编号。标签按首次出现的位置编号，保证同一状态只有一种编码。
int pack_state(int label[]) {
    int remap[8] = {};
    int next_label = 0;
    int code = 0;
    int new_has_terminal[8] = {};

    for (int i = 1; i <= p; i++) {
        int old_label = label[i];
        if (old_label == 0) {
            continue;
        }
        if (remap[old_label] == 0) {
            remap[old_label] = ++next_label;
            new_has_terminal[next_label] = (label[7] >> old_label) & 1;
        }
        code |= remap[old_label] << (3 * (i - 1));
    }
    for (int i = 1; i <= next_label; i++) {
        if (new_has_terminal[i]) {
            code |= 1 << (18 + i - 1);
        }
    }
    return code;
}

void update_next(int code, long long value) {
    if (best[code] == INF) {
        best[code] = value;
        next_codes.push_back(code);
    } else if (value < best[code]) {
        best[code] = value;
    }
}

// label[0] 是本轮离开窗口的设备；label[7] 的各 bit 记录原分量是否含用户设备。
void forget_oldest(int label[], long long value, int future_user_count) {
    int leaving_label = label[0];
    bool still_active = false;
    for (int i = 1; i <= p; i++) {
        if (label[i] == leaving_label) {
            still_active = true;
        }
    }

    if (leaving_label != 0 && !still_active && ((label[7] >> leaving_label) & 1)) {
        bool has_other_user_component = false;
        for (int i = 1; i <= p; i++) {
            int component = label[i];
            if (component != 0 && component != leaving_label
                    && ((label[7] >> component) & 1)) {
                has_other_user_component = true;
            }
        }

        // 这个分量再也无法和未来连边。它只能恰好是包含所有用户的最终连通块。
        if (!has_other_user_component && future_user_count == 0) {
            answer = min(answer, value);
        }
        return;
    }

    update_next(pack_state(label), value);
}

void transfer_one_state(const StateCost &state, int position) {
    int base_label[8] = {};
    int max_label = 0;
    for (int i = 0; i < p; i++) {
        base_label[i] = (state.code >> (3 * i)) & 7;
        max_label = max(max_label, base_label[i]);
    }
    for (int i = 1; i <= max_label; i++) {
        if ((state.code >> (18 + i - 1)) & 1) {
            base_label[7] |= 1 << i;
        }
    }

    int future_user_count = position < n ? suffix_user[position + 1] : 0;
    if (position > n) {
        base_label[p] = 0;
        forget_oldest(base_label, state.value, 0);
        return;
    }

    // 非用户设备可以完全不选。
    if (!is_user[position]) {
        base_label[p] = 0;
        forget_oldest(base_label, state.value, future_user_count);
    }

    // 选入当前设备，并枚举它分别连接哪些已有连通分量。
    int new_label = max_label + 1;
    base_label[p] = new_label;
    int min_cost[8];
    for (int i = 0; i < 8; i++) {
        min_cost[i] = INT_MAX;
    }
    for (int distance = 1; distance <= p; distance++) {
        int component = base_label[p - distance];
        if (component != 0 && edge_cost[position][distance] < min_cost[component]) {
            min_cost[component] = (int)edge_cost[position][distance];
        }
    }

    int available[6];
    int available_count = 0;
    for (int component = 1; component <= max_label; component++) {
        if (min_cost[component] != INT_MAX) {
            available[available_count++] = component;
        }
    }

    for (int mask = 0; mask < (1 << available_count); mask++) {
        int label[8];
        for (int i = 0; i < 8; i++) {
            label[i] = base_label[i];
        }
        if (is_user[position]) {
            label[7] |= 1 << new_label;
        }

        long long added_cost = 0;
        for (int k = 0; k < available_count; k++) {
            if ((mask & (1 << k)) == 0) {
                continue;
            }
            int old_label = available[k];
            added_cost += min_cost[old_label];
            if ((label[7] >> old_label) & 1) {
                label[7] |= 1 << new_label;
            }
            for (int i = 0; i < p; i++) {
                if (label[i] == old_label) {
                    label[i] = new_label;
                }
            }
        }
        forget_oldest(label, state.value + added_cost, future_user_count);
    }
}

void solve_one_case() {
    cin >> n >> m >> p;
    string users;
    cin >> users;
    for (int i = 1; i <= n; i++) {
        is_user[i] = users[i - 1] == '1';
    }
    suffix_user[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
        suffix_user[i] = suffix_user[i + 1] + is_user[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= p; j++) {
            edge_cost[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        edge_cost[v][v - u] = w;
    }

    current_states.clear();
    StateCost initial_state = {0, 0};
    current_states.push_back(initial_state);
    answer = INF;
    for (int position = 1; position <= n + p; position++) {
        next_codes.clear();
        for (int i = 0; i < (int)current_states.size(); i++) {
            transfer_one_state(current_states[i], position);
        }

        current_states.clear();
        for (int i = 0; i < (int)next_codes.size(); i++) {
            int code = next_codes[i];
            StateCost next_state = {code, best[code]};
            current_states.push_back(next_state);
            best[code] = INF;
        }
    }
    cout << answer << '\n';
}

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

    best = new long long[STATE_COUNT];
    fill(best, best + STATE_COUNT, INF);

    int test_count;
    cin >> test_count;
    while (test_count--) {
        solve_one_case();
    }

    delete[] best;
    return 0;
}

复杂度

设宽度为 $p$ 的合法窗口状态数为 $S$ 。每个状态最多枚举 $2^p$ 个连接分量集合，每次转移和状态规范化耗时 $O(p)$ ，总时间复杂度为 $O(nS2^p p)$ 。由于 $p \le 6$ ， $S$ 是常数，实际对 $n$ 线性。

代码按上界 $p=6$ 固定分配状态表：每个槽位标签编码为 3 位，并使用 6 位记录分量的用户标记，共 $2^{24}$ 个位置，约占 128MB。

总结

当图的边只会跨越很短的编号区间时，按编号扫描可以把全局连通性压缩为一个小窗口的分量划分。难点不是“是否选边”，而是设备离开窗口的瞬间必须判断：这个连通分量以后是否还有机会接回用户网络。

图示解析

这张图串起本题从带宽限制到最优网络的主线：

text

1
2
3
4
5
6
7
8边只跨越至多 p 个编号
|- 扫描设备时只保留最近 p 个设备
|  `- 状态记录窗口内的连通分量及其用户标记
|- 插入新设备：枚举它连接哪些旧分量
`- 最左设备离开窗口
   |- 无用户分量：直接丢弃
   `- 用户分量：必须继续留在窗口，或成为唯一最终分量
      `- 虚拟空设备清空窗口，得到最小费用

最左设备离开窗口后，编号差限制保证它不可能再和未来设备连边，所以此时检查用户分量是否断开是充分且必要的。窗口宽度最多为 6，连通关系的状态总数固定；每一步只需枚举新设备与窗口分量的连接集合。

时间限制： 5.0 秒

空间限制： 256 MB

题目描述

某校新建的大楼中有 $n$ 台设备，学校需要利用这些设备搭建一个网络。我们用 $1$ 到 $n$ 的整数给这些设备编号。

这些设备之间一共可以建立 $m$ 条连线，建立每条连线会消耗一定的费用。连接建立后两台设备就可以相互通信了。两台设备可以借助其他设备进行通信，即通信关系可传递：如果设备 A 和设备 B 都能与设备 C 相互通信，那么设备 A 和设备 B 也能相互通信。

由于大楼的拓扑结构所限，可以建立连线的两台设备，一定满足其编号之差的绝对值不超过 $p$ 。

这 $n$ 台设备中的一部分属于用户设备。学校要求在最终的网络中，用户设备必须两两能够相互通信，其他设备则可以根据需要选择连线或不连线。

现在问要达到学校的要求最少要消耗多少的费用。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $T$ ，表示数据的组数，保证 $T\le 5$ 。接下来依次描述每组数据。

每组数据的第一行包含三个正整数 $n, m, p$ ，表示设备的总数，可以建立的连线数量和拓扑结构的参数。

第二行包含一个长度为 $n$ 的 01 字符串，依次表示这 $n$ 台设备是否为用户设备；为 1 表示是，为 0 表示不是。相邻字符之间无空格隔开，保证不会出现除了 0 和 1 之外的字符。保证至少有 $2$ 个设备是用户设备。

接下来 $m$ 行，每行包含三个非负整数 $u, v, w$ ，表示设备 $u$ 和设备 $v$ 可以消耗 $w$ 的费用建立连线。其中 $1\le u < v ≤ n,~1\le v – u ≤ p,~0\le w ≤ 10^6$ 。

除第二行外，所有的数之间用一个空格隔开。

保证两台设备之间最多只有一条可以建立的连线，保证至少存在一种方案能够满足学校的要求。

输出格式

输出到标准输出。

对于每组数据，输出一行一个整数，表示能达到要求所需的最少费用。

input1

1
2
3
4
5
6
7
8
9
10
11
12
13
141
20 11 6
10000100001100000000
1 6 300
1 3 100
3 6 100
4 10 100
4 6 100
6 10 400
10 15 100
11 15 100
10 11 500
12 15 100
15 20 100

output1

样例 1 解释

用户设备分别是 $1,6,11,12$ 。最优的方案需要选择以下连线：设备 $1$ 和 $3$ ，费用 $100$ ；设备 $3$ 和 $6$ ，费用 $100$ ；设备 $4$ 和 $6$ ，费用 $100$ ；设备 $4$ 和 $10$ ，费用 $100$ ；设备 $10$ 和 $15$ ，费用 $100$ ；设备 $11$ 和 $15$ ，费用 $100$ ；设备 $12$ 和 $15$ ，费用 $100$ 。共计 $700$ 。

样例 2

见题目文件区的 2.in 和 2.ans。

子任务

对于所有数据，保证 $1\le n\le 500,~2\le c\le n,~1\le p\le 6$ （其中 $c$ 为用户设备总数）。

子任务 1（97 分）：传统计分，每组测试点满足以下限制：

测试点编号	$n=$	$p=$	$c=$
$1$	$500$	$6$	$n$
$2$	$500$	$6$	$2$
$3$	$500$	$6$	$4$
$4$	$500$	$6$	$6$
$5$	$500$	$6$	$10$
$6$	$500$	$2$	无限制
$7$	$500$	$2$	无限制
$8$	$500$	$3$	无限制
$9$	$500$	$6$	无限制
$10$	$500$	$6$	无限制

子任务 2（3 分）：捆绑测试，Hack 数据，无特殊限制。