问题描述
目前在一个很大的平面房间里有 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
正确解法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#include<iostream>
#include<queue>
#include<vector>
#include<set>
#include<cstring>
#include<math.h>
#define INF 1e8
using namespace std;
struct room{
int x,y;
room(int xx,int yy):x(xx),y(yy){
}
};
struct node{
int x,y,steps,kcnt;
node(int xx,int yy,int ss,int kk):x(xx),y(yy),steps(ss),kcnt(kk){
}
};
bool vis[202]={false};//n+m
vector<room> rooms;
int main(){
int n,m,k,r,x,y;
//freopen("t1.txt","r",stdin);
cin>>n>>m>>k>>r;
for(int i=0;i<n+m;i++){
cin>>x>>y;
rooms.push_back(room(x,y));
}
int sr=rooms[0].x;
int sc=rooms[0].y;
int destr=rooms[1].x;
int destc=rooms[1].y;
int ans=INF;
queue<node>q;
q.push(node(sr,sc,0,0));
while(!q.empty()){
int size=q.size();
while(size--){
node t=q.front();
q.pop();
if(t.x==destr&&t.y==destc) {
ans=min(ans,t.steps);
}
for(int j=1;j<n+m;j++){
if(vis[j]) continue;
int x=rooms[j].x;
int y=rooms[j].y;
double tmp=sqrt(pow(t.x-x,2)+pow(t.y-y,2));
if(tmp>r) continue;
if(t.kcnt>=k&&j>=n) continue;
vis[j]=true;
if(j>=n)
q.push(node(x,y,t.steps+1,t.kcnt+1));
else
q.push(node(x,y,t.steps+1,t.kcnt));
}
}
}
cout<<ans-1<<endl;
}
样例比较少的原因 所以暴力过了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#include<iostream>
#include<queue>
#include<vector>
#include<set>
#include<cstring>
#include<math.h>
#define MAX 100
#define INF 1e8
using namespace std;
struct node{
int x,y;
node(int xx,int yy):x(xx),y(yy){
}
};
bool vis[MAX]={false};//n+m
//bool vis[MAX][MAX] 是错误的
//存储的是坐标有无被访问过 可能是负数
//!!!
vector<node> room;
int main(){
int n,m,k,r,x,y;
// freopen("t1.txt","r",stdin);
cin>>n>>m>>k>>r;
for(int i=0;i<n+m;i++){
cin>>x>>y;
room.push_back(node(x,y));
}
int sr=room[0].x;
int sc=room[0].y;
int destr=room[1].x;
int destc=room[1].y;
int ans=INF;
queue<node>q;
q.push(node(sr,sc));
int steps=0;
while(!q.empty()){
int size=q.size();
while(size--){
node t=q.front();
q.pop();
int x=t.x;
int y=t.y;
if(t.x==destr&&t.y==destc) {
ans=min(ans,steps);
}
for(int c=1;c<n+m;c++){
if(vis[c]) continue;
double tmp=sqrt(pow(abs(room[c].x-x),2)+pow(abs(room[c].y-y),2));
if(tmp<=r) {
q.push(room[c]);
vis[c]=true;//!! 一维数组
}
}
}
steps++;
}
cout<<ans-1<<endl;
}
复习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#include<bits/stdc++.h>
#include<vector>
#define MAX 100
#define INF 1e8
using namespace std;
struct edge{
int x,y;
edge(int xx,int yy):x(xx),y(yy){
}
};
struct node{
int x,y,kcnt;
node(int xx,int yy,int cn):x(xx),y(yy),kcnt(cn){
}
};
int n,m,k,r;
vector<edge> g;
bool vis[MAX]={false};
int main(){
int x,y;
cin>>n>>m>>k>>r;
for(int i=0;i<n+m;i++){
cin>>x>>y;
g.push_back(edge(x,y));
}
int sr=g[0].x,sc=g[0].y;
int dsr=g[1].x,dsc=g[1].y;
int step=0,ans=INF;
int sum=0;
queue<node> qu;
qu.push(node(sr,sc,0));
while(!qu.empty()){
int size=qu.size();
while(size--){
node t=qu.front();
qu.pop();
if(t.x==dsr&&t.y==dsc) {
ans=min(ans,step);
}
for(int i=1;i<n+m;i++){
if(t.kcnt>k&&i>=n) continue;
if(vis[i]) continue;
int nx=g[i].x;
int ny=g[i].y;
if(sqrt(pow(nx-t.x,2)+pow(ny-t.y,2))>r) continue;
vis[i]=1;
if(i>=n){
qu.push(node(nx,ny,t.kcnt+1));
}
else
qu.push(node(nx,ny,t.kcnt));
}
}
step++;
}
cout<<ans-1<<endl;
}