問題描述 目前在一個(gè)很大的平面房間里有 n 個(gè)無(wú)線路由器,每個(gè)無(wú)線路由器都固定在某個(gè)點(diǎn)上。任何兩個(gè)無(wú)線路由器只要距離不超過 r 就能互相建立網(wǎng)絡(luò)連接。
　　除此以外,另有 m 個(gè)可以擺放無(wú)線路由器的位置。你可以在這些位置中選擇至多 k 個(gè)增設(shè)新的路由器。
　　你的目標(biāo)是使得第 1 個(gè)路由器和第 2 個(gè)路由器之間的網(wǎng)絡(luò)連接經(jīng)過盡量少的中轉(zhuǎn)路由器。請(qǐng)問在最優(yōu)方案下中轉(zhuǎn)路由器的最少個(gè)數(shù)是多少? 輸入格式 第一行包含四個(gè)正整數(shù) n,m,k,r。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 10⁸)。
　　接下來(lái) n 行,每行包含兩個(gè)整數(shù) x_i 和 y_i,表示一個(gè)已經(jīng)放置好的無(wú)線 路由器在 (x_i, y_i) 點(diǎn)處。輸入數(shù)據(jù)保證第 1 和第 2 個(gè)路由器在僅有這 n 個(gè)路由器的情況下已經(jīng)可以互相連接(經(jīng)過一系列的中轉(zhuǎn)路由器)。
　　接下來(lái) m 行,每行包含兩個(gè)整數(shù) x_i 和 y_i,表示 (x_i, y_i) 點(diǎn)處可以增設(shè) 一個(gè)路由器。
　　輸入中所有的坐標(biāo)的絕對(duì)值不超過 10⁸,保證輸入中的坐標(biāo)各不相同。 輸出格式 輸出只有一個(gè)數(shù),即在指定的位置中增設(shè) k 個(gè)路由器后,從第 1 個(gè)路 由器到第 2 個(gè)路由器最少經(jīng)過的中轉(zhuǎn)路由器的個(gè)數(shù)。 樣例輸入 5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0 樣例輸出 2

解題思路：這道題目最開始我是想用dp的，但是狀態(tài)感覺不太好表示，所以就用BFS+優(yōu)先隊(duì)列處理，中轉(zhuǎn)路由器個(gè)數(shù)少的排在隊(duì)列前面。可是那個(gè)系統(tǒng)居然報(bào)編譯錯(cuò)誤，還不說(shuō)明原因。。。。。無(wú)語(yǔ)。。。。希望哪位路過的大神能幫小弟我看一下。。。感激不盡！！

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;int n,m,k,r,xe,ye,xs,ys; bool vis[210]; struct Router {int x,y,id; int num; //表示使用m個(gè)位置的個(gè)數(shù)int sum; //表示目前總共用了的路由器個(gè)數(shù) }; Router rt[210];bool operator < (const Router &t1, const Router &t2) {return t1.sum > t2.sum; }int BFS() {double dis;int x,y;priority_queue<Router> q;Router now,next;for(int i = 2; i <= n+m; i++){dis = sqrt(((rt[1].x - rt[i].x)*(rt[1].x - rt[i].x) + (rt[1].y - rt[i].y)*(rt[1].y - rt[i].y))*1.0);if(dis <= r){now.x = rt[i].x; now.y = rt[i].y; now.id = i;if(i > n)now.num = 0;else now.num = 1;if(i == 2)now.sum = 0;else now.sum = 1;q.push(now);}}while(!q.empty()){now = q.top();q.pop();x = now.x, y = now.y;if(now.num > k) continue;if(now.id == 2) return now.sum;vis[now.id] = true;for(int i = 2; i <= n+m; i++){if(vis[i] == true) continue;dis = sqrt(((x - rt[i].x)*(x - rt[i].x) + (y - rt[i].y)*(y - rt[i].y))*1.0);if(dis <= r){next.x = rt[i].x; next.y = rt[i].y; next.id = i;if(i > n)next.num = now.num + 1;else next.num = now.num;if(i == 2)next.sum = now.sum;else next.sum = now.sum + 1;q.push(next);}}}return -1; }int main() { while(scanf("%d%d%d%d",&n,&m,&k,&r)!=EOF){for(int i = 1; i <= n+m; i++)scanf("%d%d",&rt[i].x,&rt[i].y);memset(vis,false,sizeof(vis));int ans = BFS();printf("%d\n",ans);}return 0; }

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

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

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