$$\color{Purple}{kuangbin题解目录}$$
描述
某国家有 $N$ 个城市,每个城市都可以看作是二维平面中的一个点,坐标为 $(x,y)$。
城市 $i$ 与城市 $j$ 之间的距离定义为 $d_{ij} = |x_i - x_j| + |y_i - y_j|$。
国王想在这 $N$ 个城市中,选出 $K$ 个城市建立飞机场。
国王希望飞机场全部建好以后,每个城市到最近机场的距离的最大值尽可能小。
也就是说,如果我们将 $d_i(1 ≤ i ≤ N)$ 定义为从城市 $i$ 到最近有机场的城市的距离,那么你的目标就是最小化 $\\max\{d_i | 1 ≤ i ≤ N \}$ 的值。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $N,K$。
接下来 $N$ 行,每行包含两个整数 $x_i,y_i$,表示第 $i$ 个城市的坐标位置。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y
,其中 $x$ 是组别编号(从 $1$ 开始),$y$ 表示最大距离的最小可能值。
数据范围
$1 \\le T \\le 100$,
$1 \\le N \\le 60$,
$1 \\le K \\le N$,
$\-10^9 \\le x_i,y_i \\le 10^9$。
输入样例:
2
3 2
0 0
4 0
5 1
4 2
0 3
1 0
3 0
8 9
输出样例:
Case #1: 2
Case #2: 4
思路
- 求最小化最大值问题,常考虑采用
二分
的思想解决,即二分城市与飞机场的距离
,若满足$k$个以内的飞机场在这个距离内能覆盖所有城市,则减小这个二分值;- 判断$k$个飞机场能否覆盖所有城市,则可考虑采用
Dancing Links
来解决,如果两个城市间的曼哈顿距离
小于二分值,则将其放入链中;- 该题的解题思路同雷达,但是该题的
坐标范围较大
,在本题中直接对距离的最大值进行二分是不足够好的,可对所有的距离值进行二分- 做法:
先把所有城市的距离用数组存下来,排序+去重,然后直接二分数组下标
即可,极大的优化了时间复杂度- 在
dance函数
中可适当剪枝,当估价函数+当前的深度>k
,直接返回$0$,若不剪枝会超时- 由于点的坐标范围是$-10^{9} \le x,y \le 10^{9}$,曼哈顿距离会爆掉
int
,故需要开成long long
代码
// Problem: 飞机场
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4242/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-17 15:43:32
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 70
#define MAXM 5000
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int t,n,k;
ll dist[MAXN][MAXN];
struct Point{
ll x;
ll y;
}s[MAXN];
ll val[MAXM];
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXM];
int f_row[MAXN];//记录每行的第一个元素
int c_cnt[MAXN];//每列元素个数
int res;
int vis[MAXN];
ll get_dist(Point a,Point b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}
int f()
{
int res=0;
memset(vis,0,sizeof(vis));
for(int i=node[0].Right;i!=0;i=node[i].Right)
if(vis[i]==0)
{
vis[i]=1;
res++;
for(int j=node[i].Down;j!=i;j=node[j].Down)
for(int k=node[j].Right;k!=j;k=node[k].Right)
vis[node[k].col]=1;
}
return res;
}
void Init_Node(int num)//初始化head和列元素,将其上下左右指针指好,行数和列数可不用初始化
{
for(int i=0;i<=num;i++)
{
node[i].Left=i-1;//左-1
node[i].Right=i+1;//右+1
node[i].Up=i;//上下指向自己
node[i].Down=i;
c_cnt[i]=0;//列个数清空
}
node[0].Left=num;//让head的左边指向最后一个的列元素
node[num].Right=0;//让最后一个的列元素的右边指向head
cnt=num;//更新结点个数
res=inf;
memset(f_row,-1,sizeof(f_row));
}
void Insert_Node(int x,int y){//插入新节点(按顺序放)
//更新具体值
node[++cnt].row=x;//更新行数
node[cnt].col=y;//更新列数
//先处理该结点的所在列链上的情况
node[cnt].Down=node[y].Down;//更新当前元素的指向下面
node[node[y].Down].Up=cnt;//之前的最后一个元素指向最后
node[cnt].Up=y;
node[y].Down=cnt;
//然后处理该结点的所在行链上的情况
if(f_row[x]<0)//表示该结点是其所在行的第一个元素
{
node[cnt].Left=cnt;//自己指向自己
node[cnt].Right=cnt;//自己指向自己
f_row[x]=cnt;//更新当前行的第一个元素
}
else//表示该结点不是其所在行的第一个元素
{
node[cnt].Right=node[f_row[x]].Right;
node[node[f_row[x]].Right].Left=cnt;
node[cnt].Left=f_row[x];
node[f_row[x]].Right=cnt;
}
c_cnt[y]++;//当前列元素+1
}
//与精准覆盖的差别在于删除、恢复和dance函数
void Remove_Link(int y)//删除该列
{
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
node[node[i].Right].Left=node[i].Left;
node[node[i].Left].Right=node[i].Right;
}
}
void Resume_Link(int y)//恢复该列
{
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
{
node[node[i].Right].Left=i;
node[node[i].Left].Right=i;
}
}
int dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(f()+depth>k)//剪枝
return 0;
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
if(depth<=k)
return 1;
else return 0;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
Remove_Link(i);//注不能是node[i].col
for(int j=node[i].Right;j!=i;j=node[j].Right)
Remove_Link(j);
if(dance(depth+1)==1)
return 1;
//先右后左
for(int j=node[i].Left;j!=i;j=node[j].Left)
Resume_Link(j);
Resume_Link(i);
}
return 0;
}
/*
void dance(int depth)//depth表示答案的个数(所搜的层数)
{
if(f()+depth>=res)//剪枝
return ;
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
res=depth;
return ;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
Remove_Link(i);//注不能是node[i].col
for(int j=node[i].Right;j!=i;j=node[j].Right)
Remove_Link(j);
dance(depth+1);
//先右后左
for(int j=node[i].Left;j!=i;j=node[j].Left)
Resume_Link(j);
Resume_Link(i);
}
}
*/
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
scanf("%d",&t);
while(t--)
{
int temp_cnt=0;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld %lld",&s[i].x,&s[i].y);
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
dist[i][j]=dist[j][i]=val[temp_cnt++]=get_dist(s[i],s[j]);
sort(val,val+temp_cnt);
temp_cnt=unique(val,val+temp_cnt)-val;
int l=0,r=temp_cnt-1;
while(l<=r)
{
Init_Node(n);
int mid=(l+r)/2;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dist[i][j]<=val[mid])
Insert_Node(i,j);
/*
dance(0);
if(res<=k)
r=mid-1;
else l=mid+1;
*/
if(dance(0)==1)
r=mid-1;
else l=mid+1;
}
printf("Case #%d: %lld\n",Cas++,val[r+1]);
}
return 0;
}