欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

无线网络

程序员文章站 2022-06-06 12:10:26
...

用到的是广度优先搜索 ,按层次遍历。
记录后来添加路由器的数量,我使用了一个add_number数组,这个量不能笼统的计数,必须是相对于路径上的上一个点。
碰到的两个坑:
一是自作聪明,将判断距离那,R*R 没考虑到超过最大整数
二是cin 比scanf运行时间长很多 真的!

#include<iostream>
#include <queue>
#include<math.h>
#define MAXN 200
using namespace std;
int N, M, K, R;
bool graph[MAXN][MAXN];  //图的邻接矩阵
int pos[MAXN][2];        //存放路由器的点坐标
bool ifedge(int a, int b)    //判断a,b两点是否有边(是否可以建立网络连接)
{
    return sqrt(pow(pos[a][0]-pos[b][0],2)+pow(pos[a][1]-pos[b][1],2))<=R;
}
int bfs()
{
    bool visited[M+N] ={0};
    int add_number[MAXN] = {0};   //记录遍历到第i个路由器时 用到添加路由器的个数
    queue<int> q;
    q.push(0);
    int len = 1,nextlen, level = 1;  //level 记录遍历的层次  len表示这一层次的个数  add_number记录添加路由器的个数
    while(1)             //由题知 输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接
    {
        nextlen =0;
        for(int l =0; l<len; l++)
        {
            int temp = q.front();
            if(temp == 1) return level-2;
            q.pop();
            for(int i=0; i<N; i++)
            {
                if(graph[temp][i] && !visited[i])
                {
                    q.push(i);
                    visited[i] = true;
                    nextlen++;
                }
            }
            for(int i=N; i<N+M ; i++)
            {
                if(graph[temp][i] && !visited[i] && add_number[temp]<K)
                {
                    q.push(i);
                    visited[i] = true;
                    add_number[i] = add_number[temp]+1;
                    nextlen++;
                }
            }
        }
        len = nextlen;
        level++ ;
    }
}
int main()
{
    cin>>N>>M>>K>>R;
    for(int i=0; i<N+M; i++)
        cin>>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] = ifedge(i, j);
    cout<<bfs();
    return 0;
}