Skip to content

Dicarbene's solutions

201403-4

Dicarbene/Solutions

试题编号： 201403-4¶

试题名称：无线网络¶

时间限制： 1.0s¶

内存限制： 256.0MB¶

问题描述¶

原题链接: http://118.190.20.162/view.page?gpid=T7

目前在一个很大的平面房间里有 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 个路由器最少经过的中转路由器的个数。

样例输入¶

样例输出¶

思路¶

这道题目的基础是通过节点之间的距离判断节点之间是否连通，求出两个节点之间所需经过的最小中转次数。

可以被看作是是图论当中的求两节点之间最短路径的问题，等同于在每对直接连通的节点之间的路径长度为1的情况下（这样求出最短路径就等同于求出最小中转次数），求出两节点之间最短路径的问题。

用结构体定义每个节点，结构体之中设置一个k值来代表当遍历到当前节点时所选的额外节点的数目，通过这个数目的大小来判断下一步应该在什么范围的节点内遍历。

AC代码¶

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define ft first
#define sd second
#define pb push_back
const int maxn = 205;
const int mod = 998244353;
long long n, m, k, r, max1=-1;
bool vis[maxn];
using namespace std;

struct node {
    long long x, y, k;
    int step;
    node () { step = k = 0; }
    node (int x1, int y1, int s1, int k1) {x=x1;y=y1;step=s1;k=k1;}
} mmp[maxn];



int bfs(int beg, int ed){
    queue<node> Q;
    Q.push(node(mmp[beg].x, mmp[beg].y, 0, 0));
    vis[beg] = true;
    while (!Q.empty()) 
    {
        node s = Q.front();Q.pop();
        if (s.x == mmp[ed].x && s.y == mmp[ed].y) return s.step - 1;//求出中转个数 
        if (s.k == k) max1=n; // 当前k值一旦到达k时只能在n里面走，不能用mmp[n]之外的节点了 
        else max1=n+m;
        for (int i=1;i<= max1;++i) 
        {
            if (vis[i]) continue;
            if ((mmp[i].x - s.x)*(mmp[i].x - s.x) + (mmp[i].y - s.y)*(mmp[i].y - s.y) > r*r) continue;//距离不够就不走 
            vis[i] = true;
            int kk;
            if(i>n)kk=s.k+1;
            else kk=s.k;//根据当前节点的类型决定是否加k值
            Q.push(node(mmp[i].x, mmp[i].y, s.step + 1, kk));
        }
    }
}
int main()
{
    cin >> n >> m >> k >> r;
    rep(i,1,n+m)
        cin >> mmp[i].x >> mmp[i].y;
    cout << bfs(1, 2);//输入结果 
    return 0;
}