本文主要是介绍2014 ACM/ICPC Asia Regional Shanghai Online E - Airport —— 二分+舞蹈链（DLX）重复覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
给你n个点，让你在其中选k个点作为特殊点，使得所有点到其中距离自己最近的特殊点的距离最大值最小，求这个值
题解：
n只有60，那么翻译一下这个就是重复覆盖问题。
那么我们只需要二分一下答案，将所有小于等于mid的值加到舞蹈链中，再跑一下即可。
注意其中的优化：
由与deep就是当前使用的点数，那么当deep>k的时候return，注意不能直接做这个判断：
if(deep+leave()>k)return;
这个判断就是说你当前加的点的基础上最少需要多少点才能完全覆盖
这个其实是很费时间的，它应当加在所有剪枝后面。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=4005;
int n;
int cnt;
int l[N],r[N],u[N],d[N],col[N],row[N];//每个点的左右上下指针，所在行列
int h[N];//每行的头结点
int s[N];//每列的节点数
int ansk[N];//选了那些集合
void init(int m){//每行m个元素for(int i=0;i<=m;i++){r[i]=i+1;l[i]=i-1;u[i]=d[i]=i;}r[m]=0;l[0]=m;memset(h,-1,sizeof(h));memset(s,0,sizeof(s));cnt=m+1;
}//初始化
void add(int R,int C){//R行C列插入点s[C]++;row[cnt]=R;col[cnt]=C;u[cnt]=C;d[cnt]=d[C];u[d[C]]=cnt;d[C]=cnt;if(h[R]==-1)h[R]=r[cnt]=l[cnt]=cnt;//该行没有点，直接加入else{r[cnt]=h[R];l[cnt]=l[h[R]];r[l[h[R]]]=cnt;l[h[R]]=cnt;}cnt++;//return;
}
void del(int c){for(int i=d[c];i!=c;i=d[i]){l[r[i]]=l[i],r[l[i]]=r[i];}
}//删除c列
void res(int c){for(int i=u[c];i!=c;i=u[i]){l[r[i]]=i,r[l[i]]=i;}
}//恢复c列
int ans;
ll dis[65][65];
int k;
int leave(){int ans=0;bool vis[n];int i,j,k;memset(vis,0,sizeof(vis));for(i=r[0];i!=0;i=r[i]){if(vis[i]==0){vis[i]=1;ans++;for(j=d[i];j!=i;j=d[j]){for(k=r[j];k!=j;k=r[k])vis[col[k]]=1;}}}return ans;
}//最优情况还要多少个集合
void dance(int deep){if(ans<=k)return ;if(deep>k)return ;if(deep+leave()>k)return;//剪枝if(r[0]==0){ans=deep;return;}int c=r[0];register int i,j;for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列for(i=d[c];i!=c;i=d[i]){ansk[deep]=row[i];del(i);for(j=r[i];j!=i;j=r[j])del(j);dance(deep+1);if(ans<=k)return ;for(j=l[i];j!=i;j=l[j])res(j);res(i);}return;
}
ll x[65],y[65];
int main()
{int t,cas=0;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);ll mi=4e9,mx=0;init(n);for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){dis[i][j]=(x[i]-x[j]>=0?x[i]-x[j]:x[j]-x[i])+(y[i]-y[j]>=0?y[i]-y[j]:y[j]-y[i]);if(i!=j)mi=min(mi,dis[i][j]),mx=max(mx,dis[i][j]);if(dis[i][j]==0)add(i,j);}}ans=1e9;dance(0);if(ans<=k){printf("Case #%d: %lld\n",++cas,0);continue;}ll l=mi,r=mx,mid;mi=4e9;while(r>=l){ans=1e9;mid=(l+r)/2;init(n);for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(dis[i][j]<=mid){add(i,j);if(i-j)add(j,i);}}}dance(0);if(ans<=k)r=mid-1,mi=mid;elsel=mid+1;}printf("Case #%d: %lld\n",++cas,mi);}return 0;
}这篇关于2014 ACM/ICPC Asia Regional Shanghai Online E - Airport —— 二分+舞蹈链（DLX）重复覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
