试题编号：	201403-4
试题名称：	无线网络
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述 　　目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网络连接。 　　除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。 　　你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少? 输入格式 　　第一行包含四个正整数 n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 10 8)。 　　接下来 n 行,每行包含两个整数 x i 和 y i,表示一个已经放置好的无线 路由器在 (x i, y i) 点处。输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。 　　接下来 m 行,每行包含两个整数 x i 和 y i,表示 (x i, y i) 点处可以增设 一个路由器。 　　输入中所有的坐标的绝对值不超过 10 8,保证输入中的坐标各不相同。 输出格式 　　输出只有一个数,即在指定的位置中增设 k 个路由器后,从第 1 个路 由器到第 2 个路由器最少经过的中转路由器的个数。 样例输入 5 3 1 3 0 0 5 5 0 3 0 5 3 5 3 3 4 4 3 0 样例输出 2

问题链接：。

问题描述：（参见上文）。

问题分析：这是一个求最优问题，通常用BFS（广度优先搜索）来实现。据称，该问题还可以用SPFA算法来实现。

程序说明：数组visited[]用于标记访问过的坐标。函数bfs()的参数是为程序通用性而设置的，就本问题而言，可以使用常量。

网友指出，程序有错，并且给出了错误的样例。据此修改了程序，后一个程序才是正解。

CCF的在线评判系统中的测试数据常常不够充分，程序有BUG照样得100分。

后一个程序增加了增设路径器的计数，如果已经用过2个，则以后不得再用增设路由器，这时只在已经设置好的路由器中搜索。参见程序中的17行的代码、50-53行的代码、以及70-73行的代码。

提交后得100分的程序如下（有BUG的100分）：

/* CCF201403-4 无线网络 */#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 100 + 100;struct {    long long x, y;} coord[N+1];struct node {    long long x, y;    int step;};bool visited[N+1];int bfs(int n, int begin, int end, long long r){    // 变量初始化    memset(visited, false, sizeof(visited));    // 设置根结点    node start, front, v;    start.x = coord[begin].x;    start.y = coord[begin].y;    start.step = 0;    queue
       
         q;    q.push(start);    // 设置根结点为已经访问过    visited[begin] = true;    while(!q.empty()) {        front = q.front();        q.pop();        // 到达终点则结束        if(front.x == coord[end].x && front.y == coord[end].y)            return front.step - 1;        // 搜索可以连接的路由器        for(int i=0; i
        
          r * r)                continue;            else {                // 第i个路由器设为已经访问过                visited[i] = true;                // 计算步数，并且将第i个路由器加入队列                v.x = coord[i].x;                v.y = coord[i].y;                v.step = front.step + 1;                q.push(v);            }        }    }    return 0;}int main(){    int n, m, k;    long long r;    // 输入数据    cin >> n >> m >> k >> r;    for(int i=0; i
         
          > coord[i].x >> coord[i].y; // BFS int ans = bfs(n + m, 0, 1, r); // 输出结果 cout << ans << endl; return 0;}/*测试数据：5 3 1 30 05 50 30 53 53 34 43 0210 1 1 20 03 1-2 0-2 2-2 4-2 60 62 62 42 22 0110 1 1 20 03 1-2 0-2 2-2 4-2 60 62 62 42 23 086 3 2 500000000 050000000 100000000100000000 100000000100000000 0100000000 5000000050000000 0-100000000 500000000 500000000 1000000002*/
         
        
       
      
     
    

提交后得100分的程序如下（正解）：

/* CCF201403-4 无线网络 */#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN = 100 + 100;struct {    long long x, y;} coord[MAXN+1];struct status {    long long x, y;    int step, kcount;};bool visited[MAXN+1];int dfs(int n, int m, int k, int begin, int end, long long r){    int max;    // 变量初始化    memset(visited, false, sizeof(visited));    // 设置根结点    status start, front, v;    start.x = coord[begin].x;    start.y = coord[begin].y;    start.step = 0;    start.kcount = 0;    queue
       
         q;    q.push(start);    // 设置根结点为已经访问过    visited[begin] = true;    while(!q.empty()) {        front = q.front();        q.pop();        // 到达终点则结束        if(front.x == coord[end].x && front.y == coord[end].y)            return front.step - 1;        // 搜索可以连接的路由器        if(front.kcount == k)            max = n;        else            max = n + m;        for(int i=0; i
        
          r * r)                continue;            else {                // 第i个路由器设为已经访问过                visited[i] = true;                // 计算步数，并且将第i个路由器加入队列                v.x = coord[i].x;                v.y = coord[i].y;                v.step = front.step + 1;                if(i >= n)                    v.kcount = front.kcount + 1;                else                    v.kcount = front.kcount;                q.push(v);            }        }    }    return 0;}int main(){    int n, m, k;    long long r;    // 输入数据    cin >> n >> m >> k >> r;    for(int i=0; i
         
          > coord[i].x >> coord[i].y; // BFS int ans = dfs(n, m, k, 0, 1, r); // 输出结果 cout << ans << endl; return 0;}/*测试数据：5 3 1 30 05 50 30 53 53 34 43 0210 1 1 20 03 1-2 0-2 2-2 4-2 60 62 62 42 22 0110 1 1 20 03 1-2 0-2 2-2 4-2 60 62 62 42 23 086 3 2 500000000 050000000 100000000100000000 100000000100000000 0100000000 5000000050000000 0-100000000 500000000 500000000 1000000002*/