問題描述 目前在一個很大的平面房間里有 n 個無線路由器,每個無線路由器都固定在某個點(diǎn)上。任何兩個無線路由器只要距離不超過 r 就能互相建立網(wǎng)絡(luò)連接。
　　除此以外,另有 m 個可以擺放無線路由器的位置。你可以在這些位置中選擇至多 k 個增設(shè)新的路由器。
　　你的目標(biāo)是使得第 1 個路由器和第 2 個路由器之間的網(wǎng)絡(luò)連接經(jīng)過盡量少的中轉(zhuǎn)路由器。請問在最優(yōu)方案下中轉(zhuǎn)路由器的最少個數(shù)是多少? 輸入格式 第一行包含四個正整數(shù) n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 10⁸)。
　　接下來 n 行,每行包含兩個整數(shù) x_i?和 y_i,表示一個已經(jīng)放置好的無線 路由器在 (x_i, y_i) 點(diǎn)處。輸入數(shù)據(jù)保證第 1 和第 2 個路由器在僅有這 n 個路由器的情況下已經(jīng)可以互相連接(經(jīng)過一系列的中轉(zhuǎn)路由器)。
　　接下來 m 行,每行包含兩個整數(shù) x_i?和 y_i,表示 (x_i, y_i) 點(diǎn)處可以增設(shè) 一個路由器。
　　輸入中所有的坐標(biāo)的絕對值不超過 10⁸,保證輸入中的坐標(biāo)各不相同。 輸出格式 輸出只有一個數(shù),即在指定的位置中增設(shè) k 個路由器后,從第 1 個路 由器到第 2 個路由器最少經(jīng)過的中轉(zhuǎn)路由器的個數(shù)。 樣例輸入 5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0 樣例輸出 2 坑題。講道理，簡單的BFS根本行不通的，因?yàn)橛衚的限制。第一次用DFS，搜索了所有的路徑并找到添加節(jié)點(diǎn)數(shù)符合小于給定k值的最小路徑，結(jié)果超時，只得了20分。后來試了下BFS，不管k的限制竟然滿分（如果k給定的小的話，這樣得到的路徑需要添加的節(jié)點(diǎn)大于k那這種情況就不符合，很明顯測試數(shù)據(jù)里的k值都不小）！！！ 不廢話了，代碼:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;vector<int> vec[205];int p[205][3];			// 0 x, 1 y , 2 類型 
int n,m,k,r;void addEdge(int a,int b){vec[a].push_back(b);vec[b].push_back(a);
}int countK = 0,minDeep=1000;
int status[205]={0};
int nodeDeep[205]={0};	
/**status 0：未遍歷，1：正在遍歷，2：完成遍歷 
**/int bfs(){queue<int> que ;que.push(0);status[0]=1;nodeDeep[0] = 0;while(que.size()>0){int nowV = que.front();que.pop();status[nowV] = 1;for(int i=0;i<vec[nowV].size();i++){int tmp = vec[nowV][i];if(status[tmp]==0){status[tmp] = 1;nodeDeep[tmp] = nodeDeep[nowV]+1;;que.push(tmp);}if(tmp==1)return nodeDeep[tmp];}status[nowV] = 2;	}}int main(){int i,j,l;cin>>n>>m>>k>>r;for(i=0;i<n+m;i++){cin>>p[i][0]>>p[i][1];p[i][2] = i>=n?1:0;}for(i=0;i<m+n-1;i++){for(j=i+1;j<m+n;j++){long long x2,y2,r2;x2 = p[i][0]-p[j][0];	x2*=x2;y2 = p[i][1]-p[j][1];	y2*=y2;r2 = r;					r2*=r2;if(x2+y2<=r2){addEdge(i,j);}}}cout<<bfs()-1<<endl;return 0;
}

　　

轉(zhuǎn)載于:https://www.cnblogs.com/jaysir/p/6146483.html

總結(jié)

以上是生活随笔為你收集整理的201403-4 无线网络的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。