CCF-CSP-201403-4 無線網路 (100分）
題目:
| 試題編號: | 2014-03-4 |
|---|---|
| 試題名稱: | 無線網路 |
| 時間限制: | 1.0s |
| 記憶體限制: | 256.0M |
| 問題描述: | 目前在一個很大的平面房間里有 n 個無線路由器,每個無線路由器都固定在某個點上， 任何兩個無線路由器只要距離不超過 r 就能互相建立網路連接， 除此以外,另有 m 個可以擺放無線路由器的位置，你可以在這些位置中選擇至多 k 個增設 的路由器， 你的目標是使得第 1 個路由器和第 2 個路由器之間的網路連接經過盡量少的中轉路由器，請問在最優方案下中轉路由器的最少個數是多少?輸入格式第一行包含四個正整數 n,m,k,r，(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 108)， 接下來 n 行,每行包含兩個整數 xi 和 yi,表示一個已經放置好的無線 路由器在 (xi, yi) 點處， 輸入資料保證第 1 和第 2 個路由器在僅有這 n 個路由器的情況下已經可以互相連接(經過一系列的中轉路由器)， 接下來 m 行,每行包含兩個整數 xi 和 yi,表示 (xi, yi) 點處可以增設 一個路由器，輸入中所有的坐標的絕對值不超過 108,保證輸入中的坐標各不相同，輸出格式輸出只有一個數,即在指定的位置中增設 k 個路由器后,從第 1 個路 由器到第 2 個路由器最少經過的中轉路由器的個數， 樣例輸入 5 3 1 3 0 0 5 5 0 3 0 5 3 5 3 3 4 4 3 0 樣例輸出 2 |
解題思路：
- 這道題目的基礎是通過節點之間的距離判斷節點之間是否連通然后求出兩個節點之間所需經過的最小中轉次數.
- 但換個角度可以被看作是是圖論當中的求兩節點之間最短路徑的問題，等同于在每對直接連通的節點之間的路徑長度為1的情況下（這樣求出最短路徑就等同于求出最小中轉次數），求出兩節點之間最短路徑的問題，這種問題可以采用Dijkastra，Spfa，Floyd等演算法，但由于路徑長度都被看作為1，因此使用bfs演算法比較方便，
- 在使用bfs演算法的情況下，如何解決確保在N+M的節點之中所選的額外節點數量不超過K個？我們需要用結構體定義每個節點，結構體之中需要設定一個k值來 代表 當遍歷到當前節點時所選的額外節點的數目，通過這個數目的大小來判斷下一步應該在什么范圍的節點內遍歷，
滿分代碼：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 205;
long long n, m, k, r, max1=-1;
bool visit[maxn] = {};//默認值為false，確保剛開始每個節點都沒有被走過
struct node {
long long x, y, k;
int step;
node () { step = k = 0; }//默認k=0
node (int x1, int y1, int s1, int k1) {x=x1;y=y1;step=s1;k=k1;}//有參建構式
} map[maxn];//用來記錄每個節點的資訊
int bfs(int begin, int end)//利用深度優先演算法遍歷來計算起點到終點
{
queue<node> Q;
Q.push(node(map[begin].x, map[begin].y, 0, 0));//起始點入站
visit[begin] = true;//true說明該節點已經走過來，避免重復節點
while (!Q.empty())
{
node s = Q.front();
Q.pop();//入堆疊
if (s.x == map[end].x && s.y == map[end].y) return s.step - 1;//求出中轉個數
if (s.k == k) max1=n; // 當前k值一旦到達k時只能在n里面走，不能用map[n]之外的節點了
else max1=n+m;//當前k值小于原k時就可以在map[n+m]里面走
for (int i=1;i<= max1;++i)
{
if (visit[i]) continue;//已經走過就不走了
if ((map[i].x - s.x)*(map[i].x - s.x) + (map[i].y - s.y)*(map[i].y - s.y) > r*r) continue;//距離不夠就不走
visit[i] = true; //距離夠了就開始準備走
int kk;
if(i>n)kk=s.k+1;
else kk=s.k;//根據當前節點的型別決定是否加k值
Q.push(node(map[i].x, map[i].y, s.step + 1, kk));//走進去,放進佇列中
}
}
}
int main()
{
cin >> n >> m >> k >> r;
for (int i = 1; i <= n + m; ++i)
{
cin >> map[i].x >> map[i].y;
}//初始化輸入
cout << bfs(1, 2);//輸入結果
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62080.html
標籤：其他
上一篇：Codeforces Round #633 (div.2) A. Filling Diamonds
下一篇：c語言單向鏈表的實作