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';
}