CCF 无线网络 100分

落日映苍穹つ 2023-05-21 15:23 17阅读 0赞

题目传送门：[http://118.190.20.162/view.page?gpid=T7][http_118.190.20.162_view.page_gpid_T7]

先记录坐标，然后把坐标转换为点，然后BFS模板+对新增中转路由器数量的限制（55行~65行）。

有了 对新增中转路由器数量的限制 会导致有些路走不通。

#include<bits/stdc++.h>
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<set>
    #include<cmath>
    using namespace std;
    const int MAXN = 204;
    const int INF = 100000000;
    
    //坐标
    struct Coord{
    	int u;
    	long long x;
    	int y;
    	Coord(int u,long long x,long long y){
    		this->u = u;
    		this->x = x;
    		this->y = y;
    	}
    };
    
    //BFS点 
    struct Node{
    	int u;
    	int step;
    	int cnt;
    	Node(int u,int step,int cnt){
    		this->u = u;
    		this->step = step;
    		this->cnt = cnt;
    	}
    }; 
    
    vector<int> adj[MAXN];  //邻接表 
    queue<Node> que;
    bool vis[MAXN];
    vector<Coord> coords;   //只用来记录，BFS遍历用不到 
    int n,k;
    
    int BFS(int s){
    	int u,v,step,cnt;
    	que.push(Node(s,0,0));
    	vis[s] = true;
    	while(!que.empty()){
    		u = que.front().u;
    		step = que.front().step;
    		cnt = que.front().cnt;
    		que.pop();
    		if(u == 2){
    			return step;
    		}
    		for(int i=0;i<adj[u].size();i++){
    			v = adj[u][i];
    			if(!vis[v]){
    				if(v > n){  //v>n，说明这是个可以新增中转路由器的点 
    					if(cnt < k){ //如果新增中转路由器的量没有超过K，那么就可以使用这个点 
    						que.push(Node(v,step+1,cnt+1));
    						vis[v] = true;
    					}
    					//否则，不再把这个点加入到BFS的遍历队列中。表示此路不通。 
    				}else{  
    					que.push(Node(v,step+1,cnt));
    					vis[v] = true;
    				}
    				
    			}
    		}
    	}
    	return -1;
    }
    
    int main(){
    	int m,u;
    	double r;
    	long long x,y,nx,ny;
    	double dis;
    	cin>>n>>m>>k>>r;
    	for(int i=1;i<=n+m;i++){
    		cin>>x>>y; //录入新坐标 
    		for(int j=0;j<coords.size();j++){  //遍历之前录入的坐标 
    			u = coords[j].u;
    			nx = coords[j].x;
    			ny = coords[j].y;
    			dis = sqrt( (x-nx)*(x-nx) + (y-ny)*(y-ny) ); //计算两个坐标的距离 
    			if(dis<=r){   //距离小于r，说明两个坐标可以建立网络连接 
    				adj[u].push_back(i);
    				adj[i].push_back(u);
    			}
    		}
    		coords.push_back(Coord(i,x,y));
    	}
    	cout<<BFS(1)-1<<endl;
    	return 0;
    }

[http_118.190.20.162_view.page_gpid_T7]: http://118.190.20.162/view.page?gpid=T7