这一道题和HDU2295是一样
是一个dancing links重复覆盖解决最小支配集的问题
在给定长度下求一个最小支配集，只要小于k就行
然后就是二分答案，每次求最小支配集
只不过HDU2295是浮点，这里是整数
我写的一个比较暴力
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; typedef long long LL; const int N=4e3; int n,m,sz,k; int u[N],l[N],r[N],d[N]; int h[65],s[65],col[N]; void init() { for(int i=0; i<=m; ++i) { s[i]=0; u[i]=d[i]=i; l[i]=i-1; r[i]=i+1; } r[m]=0; l[0]=m; sz=m; for(int i=1; i<=n; ++i) h[i]=-1; } void link(int x,int y) { ++sz; ++s[y],col[sz]=y; u[sz]=u[y],d[u[y]]=sz; d[sz]=y,u[y]=sz; if(h[x]==-1)h[x]=l[sz]=r[sz]=sz; { l[sz]=l[h[x]]; r[l[h[x]]]=sz; r[sz]=h[x]; l[h[x]]=sz; } } void del(int y) { for(int i=d[y]; i!=y; i=d[i]) r[l[i]]=r[i],l[r[i]]=l[i]; } void resume(int y) { for(int i=d[y]; i!=y; i=d[i]) r[l[i]]=l[r[i]]=i; } bool vis[65]; int f() { int ret=0; for(int i=r[0]; i; i=r[i]) vis[i]=0; for(int i=r[0]; i; i=r[i]) { if(vis[i])continue; vis[i]=1; ++ret; for(int j=d[i]; j!=i; j=d[j]) for(int k=r[j]; k!=j; k=r[k]) vis[col[k]]=1; } return ret; } bool dance(int pos) { if(pos+f()>k)return 0; if(!r[0]) { if(pos<=k) return 1; return 0; } int t=r[0]; for(int i=r[0]; i!=0; i=r[i]) if(s[i]<s[t])t=i; for(int i=d[t]; i!=t; i=d[i]) { del(i); for(int j=r[i]; j!=i; j=r[j]) del(j); if(dance(pos+1))return 1; for(int j=l[i]; j!=i; j=l[j]) resume(j); resume(i); } return 0; } struct point { LL x,y; }o[65]; LL ABS(LL x,LL y) { if(x>=y)return x-y; return y-x; } LL dis(point a,point b) { return ABS(a.x,b.x)+ABS(a.y,b.y); } LL D[N]; int main() { int T,cas=0; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k),m=n; for(int i=1;i<=n;++i) scanf("%I64d%I64d",&o[i].x,&o[i].y); int cnt=0; for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) D[++cnt]=dis(o[i],o[j]); sort(D+1,D+1+cnt); cnt=unique(D+1,D+1+cnt)-D-1; int high=cnt,low=0,mid; while(low<high) { mid=(low+high)>>1; init(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(dis(o[i],o[j])<=D[mid]) link(i,j); if(dance(0))high=mid; else low=mid+1; } printf("Case #%d: %I64d ",++cas,D[low]); } return 0; }
然后另一个是离散化的
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; typedef long long LL; const int N=4e3; int n,m,sz,k; int u[N],l[N],r[N],d[N]; int h[65],s[65],col[N]; void init() { for(int i=0; i<=m; ++i) { s[i]=0; u[i]=d[i]=i; l[i]=i-1; r[i]=i+1; } r[m]=0; l[0]=m; sz=m; for(int i=1; i<=n; ++i) h[i]=-1; } void link(int x,int y) { ++sz; ++s[y],col[sz]=y; u[sz]=u[y],d[u[y]]=sz; d[sz]=y,u[y]=sz; if(h[x]==-1)h[x]=l[sz]=r[sz]=sz; { l[sz]=l[h[x]]; r[l[h[x]]]=sz; r[sz]=h[x]; l[h[x]]=sz; } } void del(int y) { for(int i=d[y]; i!=y; i=d[i]) r[l[i]]=r[i],l[r[i]]=l[i]; } void resume(int y) { for(int i=d[y]; i!=y; i=d[i]) r[l[i]]=l[r[i]]=i; } bool vis[65]; int f() { int ret=0; for(int i=r[0]; i; i=r[i]) vis[i]=0; for(int i=r[0]; i; i=r[i]) { if(vis[i])continue; vis[i]=1; ++ret; for(int j=d[i]; j!=i; j=d[j]) for(int k=r[j]; k!=j; k=r[k]) vis[col[k]]=1; } return ret; } bool dance(int pos) { if(pos+f()>k)return 0; if(!r[0]) { if(pos<=k) return 1; return 0; } int t=r[0]; for(int i=r[0]; i!=0; i=r[i]) if(s[i]<s[t])t=i; for(int i=d[t]; i!=t; i=d[i]) { del(i); for(int j=r[i]; j!=i; j=r[j]) del(j); if(dance(pos+1))return 1; for(int j=l[i]; j!=i; j=l[j]) resume(j); resume(i); } return 0; } struct point { LL x,y; }o[65]; LL ABS(LL x,LL y) { if(x>=y)return x-y; return y-x; } LL dis(point a,point b) { return ABS(a.x,b.x)+ABS(a.y,b.y); } LL D[N]; int main() { int T,cas=0; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k),m=n; for(int i=1;i<=n;++i) scanf("%I64d%I64d",&o[i].x,&o[i].y); int cnt=0; for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) D[++cnt]=dis(o[i],o[j]); sort(D+1,D+1+cnt); cnt=unique(D+1,D+1+cnt)-D-1; int high=cnt,low=0,mid; while(low<high) { mid=(low+high)>>1; init(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(dis(o[i],o[j])<=D[mid]) link(i,j); if(dance(0))high=mid; else low=mid+1; } printf("Case #%d: %I64d ",++cas,D[low]); } return 0; }