CCF201403-4：无线网络（建图+bfs）

忘是亡心i 2022-05-16 01:57 178阅读 0赞

题目链接：  
[无线网络][Link 1]

题目大意：  
中文题大概不用翻译吧！抽象出模型大概就是给你n个点（点分两种点，原来就有的点，可添加的点，对应题目），然后好多边（如果两个点之间的距离不超过r我们就建立一条边），要求找出点1经过最少几个点就可以到达点2。

解题思路：

### 一、建立模型 ###

读完题，感觉像是几何题，但是细想，当作几何来做的话，并不好下手。通过题目给定的条件，两点距离不超过r就可以建立连接，我们可以把它抽象出一张图。  
建图中先不讨论点的区别，只要两点距离不超过r都建一条边，这样题目就变成一道求最短路的题了

### 二、bfs求最短路 ###

核心思想和普通求bfs一样，唯一需要添加条件的是，记录每个点的最短路径上经过了多少个不是本来就存在的点（即可添加的基站），如果当前节点已经经过了k个可添加点，那么就不能再走可添加点的路线)

代码中用一个数组numK\[i\]记录节点i经过了几个可添加点  
flag\[i\]:标记节点i是否是可添加点

如果当前节点为可添加点则 numK\[v\] = numK\[tmp\] +1; （tmp为父节点）  
else numk\[v\] =numK\[tmp\]+1

### 三、一些坑 ###

需要用long long ，不然求两点间距离会爆了int，然后数组尽量开大一点233333！！！！

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <vector> 
    #include <algorithm>
    #include <cmath>
    #include <queue>
    
    using namespace std;
    
    long long n,m,k,r;
    int dep[500],numK[500],flag[500];
    
    struct node{
        int v;
        int t;
        node(){};
        node(int _u, int _t):v(_u),t(_t){};
    };
    
    vector<node> g[500];
    
    struct point{
        long long x;
        long long y;
        point(){};
        point(long long _x, long long _y):x(_x),y(_y){};
    }p[550];
    
    queue<int> q;
    
    void bfs(int u){
        q.push(u);
        while(!q.empty()){
            int tmp = q.front();
            q.pop();
            for(int j=0; j<g[tmp].size(); ++j){
                int v = g[tmp][j].v;
                if(dep[v]==0&&(numK[tmp]<k||!flag[v])){
                //  if(v==2) cout<<tmp<<endl;
                    dep[v] = dep[tmp] + 1;
                    if(flag[v]) numK[v] = numK[tmp] + 1;
                    else numK[v] = numK[tmp];
                    q.push(v);
                }
            }
        }
    }
    
    long long getDist(point a, point b){
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
    
    void init(){
        memset(dep, 0, sizeof(dep));
        memset(numK, 0, sizeof(numK));
        memset(flag, 0, sizeof(flag));
        for(int i=0; i<200; ++i) g[i].clear();
        dep[1] = 1;
    }
    
    int main(){
        init();
        scanf("%lld%lld%lld%lld",&n,&m,&k,&r);
        int cnt = 0;
        for(int i=0; i<n; ++i){
            long long x,y;
            scanf("%lld%lld",&x,&y);
            p[++cnt] = point(x,y);
            flag[cnt]=0;
            for(int j=1; j<cnt; ++j){
                if(getDist(p[cnt], p[j])<=r*r){
                    g[cnt].push_back(node(j,0));
                    g[j].push_back(node(cnt,0));
                }
            }
        }
    
        for(int i=0; i<m; ++i){
            long long x,y;
            scanf("%lld%lld",&x,&y);
            p[++cnt] = point(x,y);
            flag[cnt]=1;
            for(int j=1; j<cnt; ++j){
                if(getDist(p[cnt], p[j])<=r*r){
                    g[cnt].push_back(node(j,1));
                    g[j].push_back(node(cnt,1));
                }
            }
        }
    
        bfs(1);
        cout<<dep[2]-2<<endl;
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T7