Day3

题目描述

目前在一个很大的平面房间里有 \(n\) 个无线路由器，每个无线路由器都固定在某个点上。

任何两个无线路由器只要距离不超过 \(r\) 就能互相建立网络连接。

除此以外，另有 \(m\) 个可以摆放无线路由器的位置。

你可以在这些位置中选择至多\(k\) 个增设新的路由器。

你的目标是使得第 \(1\) 个路由器和第 \(2\)个路由器之间的网络连接经过尽量少的中转路由器。

请问在最优方案下中转路由器的最少个数是多少?

输入格式

第一行包含四个正整数 \(n,m,k,r\)。

接下来 \(n\) 行，每行包含两个整数 \(x_i\) 和 \(y_i\)，表示一个已经放置好的无线路由器在\((x_i,y_i)\)
点处。输入数据保证第 \(1\) 和第 \(2\) 个路由器在仅有这 \(n\)个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。

接下来 \(m\) 行，每行包含两个整数 \(x_i\) 和 \(y_i\)，表示 \((x_i,y_i)\)点处可以增设一个路由器。

输入中所有的坐标的绝对值不超过 \(10^8\)，保证输入中的坐标各不相同。

输出格式

输出只有一个数，即在指定的位置中增设 \(k\) 个路由器后，从第 \(1\) 个路由器到第 \(2\)个路由器最少经过的中转路由器的个数。

数据范围

\(2≤n≤100,1≤k≤m≤100,1≤r≤10^8\)

输入样例：

5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0

输出样例：

2

题目分析

\(bfs+dp\) 或 树形\(dp\)

先建图，将可以通信的两点间连线，因为\(n \le 100\) 所以用邻接矩阵存就行
然后对于图上的点来说，有两类，一类是有花费的，另一类是无花费的。
然后我们求走有花费的点的最短路

这道题很像NOIP 2017 普及组T3 棋盘

其实抽象一下，就是类似于有步数限制的单源汇最短路，但不是所有点都有花费
那么我们就得有两个状态，一个是走到点的单源汇最短路，另一个是花费，且最后结果花费要小于\(k\)
由此想到\(dp\)
\(dp(i , j)\)表示走到\(i\)点，花费点为\(j\)的最小步数
那么对于\(dp(i , j)\)能转移的状态就是他的邻接节点，如果该点有花费，那么转移就得是\(j - - 1\)转移到\(j\)即可
至于遍历图，算单源汇最短路，那就很简单了，数据很小，用\(bfs\)就行

注：一共是\(n + m\)个点所以开\(210\)个空间

C++ 代码

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second

using namespace std;

const int N = 210;

typedef pair<int, int> PII;

int n , m , k , r;
bool is_cost[N];
PII p[N];
bool st[N][N];
int idx , dp[N][N];
bool g[N][N];

bool check(PII a , PII b)
{
    int dist = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    return r >= dist;
}

void bfs()
{
    memset(dp , 0x3f , sizeof dp);
    dp[1][0] = 0;
    queue<PII> q;
    q.push({1 , 0});
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int ver = t.x , cost = t.y;
        if(st[ver][cost]) continue;
        st[ver][cost] = true;
        for(int i = 1 ; i <= idx ; i ++)
            if(g[ver][i] && cost + is_cost[i] <= k && !st[i][cost + is_cost[i]] && dp[i][cost + is_cost[i]] >= dp[ver][cost] + 1)
            {
                dp[i][cost + is_cost[i]] = dp[ver][cost] + 1;
                q.push({i , cost + is_cost[i]});
            }
    }
}

signed main()
{
    cin >> n >> m >> k >> r;
    r *= r;
    int a , b;
    for(int i = 1 ; i <= n ; i ++)
    {
        cin >> a >> b;
        p[++ idx] = {a , b};
        is_cost[idx] = false;
    }
    
    for(int i = 1 ; i <= m ; i ++)
    {
        cin >> a >> b;
        p[++ idx] = {a , b};
        is_cost[idx] = true;
    }
    
    for(int i = 1 ; i <= idx ; i ++)
        for(int j = i + 1 ; j <= idx ; j ++)
            if(check(p[i] , p[j]))
                g[i][j] = g[j][i] = 1;
    
    bfs();
    
    int ans = 210;
    
    for(int i = 0 ; i <= k ; i ++)
        ans = min(ans , dp[2][i] - 1);
    cout << ans << '\n';
}