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
这个题，怎么说呢，先上来看是懵逼的，直接被吓到了，感觉巨难，根本不知道怎么做，搜了搜题解也是各种解法，有的很长有的比较短，于是乎我就找了个短的开始研究，开始还是很痛苦的，一会也可以贴上大神的代码以及我读代码的时候加的注释，简直了。其中有一段可读性不好，让我理解了半天，最后理解了之后改变一下表达方式，果然清晰了很多。这题的主要思路是spfa，但是具体如何spfa是很有讲究的呀╮(╯▽╰)╭。读题的时候建图就把我吓到了，其实很简单，两重for循环，判断每个点之间的距离是不是小于规定的距离（这么暴力的法主要是怕超时），如果是，就说明两个点是联通的，直接让邻接矩阵的对应项赋值为1即可，图建好了，就可以进行spfa了。这里最有讲究的，就是d和vis数组，并不像平常的d和vis数组，代码中也有注释，即d[i][j]表示从起点开始，经过增设的j个点，到达第i个点的最短路径，vis[i][j]表示是否可以从起点经过增设的j个路由器到达i。其实看起来还不是很懂，但是实际上，这个d和平常的一维的d基本上没有任何区别，仍旧是表示从一个点到另一个点的距离，只是这里有判断到底经过了几个增设的点，然后后面的j的主要功能还是在松弛的时候判断是不是比规定的k个点多了，如果多了就直接不入队（啊，刚才看代码貌似还有一个用处，就是来表示经过不同数量的增设点可能有不同的距离，嗯，这点是很重要的）。vis数组的功能也和d差不多了。总之，这题真的看出思路和经验，方法又常规又巧妙，确实值得琢磨，也感受到自己与高手的实力差距。
以下是大神的简短代码以及我冗长的注释
//虽然被那两个题搞得有点不敢做题，但是比赛的时候该做还是要做的呀，毕竟如果思路对了的话
//再怎么说RP差也是会得分的吧
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define N 205
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
struct P {
int x,y;
} p[N];
int n,m,k,r;
int d[N][N];
bool vis[N][N],Map[N][N];
void spfa() {
queue<P> q;
memset(vis,0,sizeof(vis));
memset(d,INF,sizeof(d));
//这里的d[i][j]和vis[i][j]有特殊的含义
// d[i][j]表示从起点开始，经过增设的j个点，到达第i个点的最短路径
// vis[i][j]表示是否可以从起点经过增设的j个路由器到达i
d[0][0]=0;
vis[0][0]=1;
//这里的s和tem感觉已经不再是表示一个点了，所以有点错觉
P s,tem;
int des_p=0,ap_num=0;
int tp_des_p,tp_ap_num;
s.x=s.y=des_p;
q.push(s);
while(!q.empty()) {
s=q.front();
q.pop();
des_p=s.x;
ap_num=s.y;
vis[des_p][ap_num]=0;
for(int i=0; i<n+m; ++i)
//和s点相连的点
//另外看到这里莫名感觉这题简单（什么都不会，但有一种莫名的自信）
//这哪是spfa啊，更像是普通的bfs（写完我就后悔了= =）
//这里的s.x其实就是点的编号。程序可读性差= =（明明可以用别的表示的，非得图省事用P，差评！）
//嗯……这个程序有点带劲啊╮(╯▽╰)╭
if(Map[des_p][i]) {
//下面这几句是重点啊
tp_des_p=i;
tp_ap_num=ap_num;
if(i>=n) ++tp_ap_num;
if(tp_ap_num<=k && d[tp_des_p][tp_ap_num]>d[des_p][ap_num]+1) {
//只要符合以上条件就进行松弛
d[tp_des_p][tp_ap_num]=d[des_p][ap_num]+1;
//如果不在队列里就让其进入队列
if(!vis[tp_des_p][tp_ap_num]) {
vis[tp_des_p][tp_ap_num]=1;
//进入队列的其实是起点所到目的地点和经过的增设点数
tem.x=tp_des_p;
tem.y=tp_ap_num;
q.push(tem);
}
}
}
}
int ans=INF;
for(int i=0; i<=k; i++) ans=min(ans,d[1][i]);
printf("%d\n",ans-1);
}
int main() {
int i,j;
cin>>n>>m>>k>>r;
//输入存在的点和可以放置的点
for(i=0; i<n+m; ++i) scanf("%d%d",&p[i].x,&p[i].y);
//map是邻接矩阵
memset(Map,0,sizeof(Map));
//这个循环看起来不免重复，但是没超时
for(i=0; i<n+m; ++i)
for(j=i+1; j<n+m; ++j)
//LL就是long long int，这里是强制类型转换
if(LL(p[i].x-p[j].x)*(p[i].x-p[j].x)+LL(p[i].y-p[j].y)*(p[i].y-p[j].y)<=LL(r)*r)
Map[i][j]=Map[j][i]=1;
spfa();
return 0;
}其实本来不是这样的，本来是直接用的s.x和s.y来进行操作的，确实意思混淆了。另外，原谅我些许的逗比，毕竟学不会的时候是很蛋疼的。
然后下面是我的代码，虽然几乎是一样的，但毕竟是自己写哒，看起来亲切一些╮(╯▽╰)╭
另外解释下命名= =，des_p就是destination point的缩写，表示目的地点，ap_num就是 added point number的缩写（语法可能不太对= =），表示通过的增设点的数量
#include<iostream>
#include<queue>
#include<cstring>
#define MAX 100000001
#define N 205
using namespace std;
typedef long long int LL;
int d[N][N];
bool vis[N][N];
bool arcs[N][N];
struct P{
int x,y;
}p[N];
struct P_D{
int des_p;
int ap_num;
};
int m,n,k,r;
queue<struct P_D> q;
void spfa(){
memset(d,MAX,sizeof(d));
struct P_D s;
struct P_D temp;
s.des_p=0;
s.ap_num=0;
q.push(s);
vis[0][0]=1;
d[0][0]=0;
while(!q.empty()){
s=q.front();
q.pop();
vis[s.des_p][s.ap_num]=0;
for(int i=0;i<n+m;i++)
if(arcs[s.des_p][i]){
temp.des_p=i;
temp.ap_num=s.ap_num;
if(i>=n) temp.ap_num++;
if(temp.ap_num<=k && d[temp.des_p][temp.ap_num]>d[s.des_p][s.ap_num]+1){
d[temp.des_p][temp.ap_num]=d[s.des_p][s.ap_num]+1;
if(!vis[temp.des_p][temp.ap_num]){
vis[temp.des_p][temp.ap_num]=1;
q.push(temp);
}
}
}
}
int ans=MAX;
for(int i=0;i<=k;i++) ans=min(ans,d[1][i]);
cout<<ans-1;
}
int main(){
cin>>n>>m>>k>>r;
for(int i=0;i<n+m;i++)
cin>>p[i].x>>p[i].y;
for(int i=0;i<n+m;i++)
for(int j=i+1;j<n+m;j++)
if( (LL)(p[i].x-p[j].x)*(p[i].x-p[j].x)+(LL)(p[i].y-p[j].y)*(p[i].y-p[j].y)<=(LL)r*r)
arcs[i][j]=arcs[j][i]=1;
spfa();
return 0;
}