CCF 201403-4 无线网络

  • 作者:Moilk
  • 最后编辑:2016年09月05日
  • 标签: CCF 算法

问题描述
  目前在一个很大的平面房间里有 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

解题说明
  首先根据点与点之间的距离是不是超过r来建图,用邻接矩阵保存。然后用bfs从1点出发搜索点2。P类中,x为节点id,ck用于控制新增节点的个数不超过k,step记录步数。

#include <iostream>
#include <queue>

using namespace std;

struct Pn2 {
	int x;
	int y;
};

struct P{
	int x;
	int ck;
	int step;
	P(int xx=0,int c=0,int s=0){
		x=xx,ck=c,step=s;
	}
};

bool connected(Pn2 p1,Pn2 p2,long long rr) {
	long long xx=p1.x-p2.x;
	long long yy=p1.y-p2.y;
	if((xx*xx+yy*yy)<=rr) {
		return true;
	}
	return false;
}

bool map[200][200]= {0};
bool vis[200]= {0};
int n,m,k;
long long r;

int bfs() {
	P p,tmp;
	queue<P> sp;
	sp.push(P());
	int sum=n+m;
	int res=0,ck=0;
	while(!sp.empty()) {
		p=sp.front();
		vis[0]=1;
		sp.pop();
		for(int i=1; i<sum; i++) {
			if(p.ck==k&&i>=n){
				continue;
			}
			if(map[p.x][i]) {
				if(!vis[i]) {
					vis[i]=1;
					if(i==1) {
						return p.step;
					}
					tmp=p;
					tmp.x=i;
					tmp.step++;
					if(i>=n) {
						tmp.ck++;
					}
					sp.push(tmp);
				}
			}
		}
	}

	return -1;
}

int main(void) {
	Pn2 pns[200];

	cin>>n>>m>>k>>r;
	int sum=n+m;
	for(int i=0; i<sum; i++) {
		cin>>pns[i].x>>pns[i].y;
	}
	long long rr=r*r;
	for(int i=0; i<sum-1; i++) {
		for(int j=i+1; j<sum; j++) {
			if(connected(pns[i],pns[j],rr)) {
				map[i][j]=map[j][i]=1;
			}
		}
	}
	cout<<bfs()<<endl;

	return 0;
}