csp 201403_4 无线网络

摘要:

最短路径 bfs

问题描述

  目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网络连接。除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。
  你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少?

输入格式

  第一行包含四个正整数 n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 108)。
  接下来 n 行,每行包含两个整数 xi 和 yi,表示一个已经放置好的无线 路由器在 (xi, yi) 点处。输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。
  接下来 m 行,每行包含两个整数 xi 和 yi,表示 (xi, yi) 点处可以增设 一个路由器。
  输入中所有的坐标的绝对值不超过 108,保证输入中的坐标各不相同。

输出格式

  输出只有一个数,即在指定的位置中增设 k 个路由器后,从第 1 个路 由器到第 2 个路由器最少经过的中转路由器的个数。

样例输入

5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0

样例输出

2

思路

路由器构成了一个图,如果两个路由器之间的距离小于r则存在边。问题要求解的是最短路径,所有边的权都为1,考虑使用BFS。搜索时要记录已经增设的路由器数量,确保路由器数量不超过k。

AC代码

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
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#define MAXN 210
using namespace std;

struct node
{
int num; //序号
int new_router_num; //新增路由器数量
int length; //路径长度
node(int a, int b, int c):num(a), new_router_num(b), length(c){} //构造函数
};


int N, M, K, R;
bool graph[MAXN][MAXN]; //graph[i][j]的值代表着第i个点和第j个点之间是否有边,即第i个点与第j个点之间的距离是否小于r
int pos[MAXN][2]; //每行代表一个元素,两列分别是x坐标和y坐标

bool inRange(int a, int b, int R) {
return sqrt(pow(pos[a][0]-pos[b][0],2)+pow(pos[a][1]-pos[b][1],2))<=R;
}

int bfs(int s, int t) {
vector<bool> visited(M+N); //记录某结点是否被访问过
queue<node > q;
node start(s, 0, 1);
q.push(start);
while(!q.empty()) {
node f = q.front();
if(f.num == t) return f.length-2; //到达了终点
q.pop();
for(int i=0; i<N; i++) { //不考虑新增路由器的情况下选择路径的下一个结点
if(graph[f.num][i] && !visited[i]) {
node temp(i, f.new_router_num, f.length + 1); //因为不考虑新增路由器,所以f.new_router_num不变
q.push(temp);
visited[i] = true;
}
}
for(int i=N; i<N+M; i++) { //仅考虑新增路由器的情况下选择路径的下一个结点
if(graph[f.num][i] && !visited[i] && f.new_router_num<K) {
node temp(i, f.new_router_num + 1, f.length + 1);
q.push(temp);
visited[i] = true;
}
}
}
return -1;
}

int main() {
scanf("%d%d%d%d", &N, &M, &K, &R);
for(int i=0; i<N+M; i++) {
scanf("%d%d", &pos[i][0], &pos[i][1]);
}
for(int i=0; i<N+M; i++) {
for(int j=i+1; j<N+M; j++) {
graph[i][j] = graph[j][i] = inRange(i, j, R);
}
}
printf("%d", bfs(0, 1));
}