无线网络

形式化题目

给定 $n$ 个已有路由器和 $m$ 个候选位置，距离不超过 $r$ 的两点可以互连。在候选位置中最多增设 $k$ 个路由器，求路由器 1 到路由器 2 经过的最少中转路由器数。

思路

先看枚举每个候选点选或不选的暴力：

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/**
 * 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:51
 */
// brute.cpp：小数据暴力解，枚举每个候选位置是否增设路由器。
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 205;
const int INF = 0x3f3f3f3f;

int n, m, k;
long long r;
long long x[MAXV], y[MAXV];
vector<int> graph[MAXV];
int choose[MAXV];
int best;

bool can_connect(int a, int b) {
    long long dx = x[a] - x[b];
    long long dy = y[a] - y[b];
    return dx * dx + dy * dy <= r * r;
}

int shortest_path() {
    int dist[MAXV];
    memset(dist, 0x3f, sizeof(dist));
    queue<int> q;
    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)graph[u].size(); i++) {
            int v = graph[u][i];
            if (v > n && !choose[v - n]) {
                continue;
            }
            if (dist[v] != INF) {
                continue;
            }
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }

    return dist[2];
}

void dfs(int pos) {
    if (pos > m) {
        int added = 0;
        for (int i = 1; i <= m; i++) {
            added += choose[i];
        }
        if (added > k) {
            return;
        }
        best = min(best, shortest_path());
        return;
    }

    choose[pos] = 0;
    dfs(pos + 1);
    choose[pos] = 1;
    dfs(pos + 1);
}

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

    cin >> n >> m >> k >> r;
    int total = n + m;
    for (int i = 1; i <= total; i++) {
        cin >> x[i] >> y[i];
    }

    for (int i = 1; i <= total; i++) {
        for (int j = i + 1; j <= total; j++) {
            if (can_connect(i, j)) {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }

    best = INF;
    dfs(1);
    cout << best - 1 << '\n';
    return 0;
}

它有 $2^m$ 种选择，无法处理 $m=100$ 。

把资源使用量放进状态

把所有旧路由器和候选位置建成无向图。关键是把“新增数量”放进路径状态：(u, used) 表示当前在节点 u，已经经过 used 个候选路由器。走到旧路由器不改变 used，走到候选路由器则加一，超过 k 的状态不进入队列。

从 (1,0) 做 BFS，得到每个状态的最少边数。最终在 dist[2][0..k] 中取最小值；若路径有 d 条边，中转路由器数量是 d-1。

样例状态 BFS

下表展示不同新增数量下到达路由器 2 的最短状态：

使用新增路由器数	到达路由器 2 的最短边数	中转路由器数
0	4	3
1	3	2

状态 (节点, used) 分开记录同一个节点在不同预算下的距离。样例中使用 1 个候选路由器后，最优中转数从 3 降为 2。

代码

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/**
 * 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:51
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 205;
const int MAXK = 105;
const int INF = 0x3f3f3f3f;

int n, m, k;
long long r;
long long x[MAXV], y[MAXV];
vector<int> graph[MAXV];
int dist[MAXV][MAXK];

bool can_connect(int a, int b) {
    long long dx = x[a] - x[b];
    long long dy = y[a] - y[b];
    return dx * dx + dy * dy <= r * r;
}

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

    cin >> n >> m >> k >> r;
    int total = n + m;
    for (int i = 1; i <= total; i++) {
        cin >> x[i] >> y[i];
    }

    for (int i = 1; i <= total; i++) {
        for (int j = i + 1; j <= total; j++) {
            if (can_connect(i, j)) {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }

    memset(dist, 0x3f, sizeof(dist));
    queue<pair<int, int> > q;
    dist[1][0] = 0;
    q.push(make_pair(1, 0));

    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();

        int u = now.first;
        int used = now.second;
        for (int i = 0; i < (int)graph[u].size(); i++) {
            int v = graph[u][i];
            int next_used = used + (v > n);
            if (next_used > k || dist[v][next_used] != INF) {
                continue;
            }

            dist[v][next_used] = dist[u][used] + 1;
            q.push(make_pair(v, next_used));
        }
    }

    int answer = INF;
    for (int used = 0; used <= k; used++) {
        answer = min(answer, dist[2][used]);
    }

    // 路径有 answer 条边，去掉两端路由器后剩下 answer - 1 个中转。
    cout << answer - 1 << '\n';
    return 0;
}

复杂度

设总节点数 $V=n+m$ 、边数为 $E$ 。建图为 $O(V^2)$ ，状态 BFS 为 $O(kE)$ ，总空间为 $O(E+Vk)$ 。

总结

当路径有一个“最多使用多少个资源”的限制时，可以把资源使用量加入 BFS 状态。这里几何只负责建图，最短路负责在预算内选择路线。

图示解析

这张图串起本题从几何连接到资源限制最短路的主线：

text

1
2
3
4
5两点距离不超过 r
`- 建成无向图，旧路由器代价 0，候选路由器代价 1
   `- 状态 = (当前节点, 已使用候选数)
      `- 在状态图上 BFS 求最少边数
         `- 所有 used <= k 中取最小值，再减 1

几何判断只负责建立图，路径优化发生在“节点 + 资源使用量”的状态空间中。把候选节点是否使用融入路径状态后，不需要枚举所有候选集合。减去 1 是因为最短路径的边数包含起点到终点之间的两端连接，而题目只数中转路由器。

目录

形式化题目

思路

把资源使用量放进状态

样例状态 BFS

代码

复杂度

总结

图示解析