題意:給定n個城市的坐标,要在城市中建k個飛機場,使任意城市距離最近的飛機場的最大值最小,求這個最小距離。
思路:最大值最小化是典型二分條件,然後就是如何check,将每對距離小于二分值的兩個機場稱為互相可覆寫,構造n * n的矩陣,機場之間有覆寫關系的置為1,否則為0,則轉化為DLX求解矩陣可重複覆寫問題。
DLX精确覆寫詳解:點選打開連結 (想不會都難)
DLX重複覆寫與精确覆寫:點選打開連結
然後就是本題如果純套模闆的話還是很卡時間上限的,但是隻要稍微了解模闆的思路,改改遞歸條件就能快3-5倍時間,學算法還是不能隻會用模闆啊!
emmmm,模闆是我從網上扒的,重複覆寫和精确覆寫寫在一起了,還是挺好用的。
代碼(純模闆1045ms):
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> P;
const int inf = 0x3f3f3f3f;
struct DLX{
const static int maxn=3636;
#define FF(i,A,s) for(int i = A[s];i != s;i = A[i])
int L[maxn],R[maxn],U[maxn],D[maxn];
int size,col[maxn],row[maxn],s[maxn],H[maxn];
bool vis[66];
int ans[maxn],cnt;
void init(int m){
for(int i=0;i<=m;i++){
L[i]=i-1;R[i]=i+1;U[i]=D[i]=i;s[i]=0;
}
memset(H,-1,sizeof(H));
L[0]=m;R[m]=0;size=m+1;
}
void link(int r,int c){
U[size]=c;D[size]=D[c];U[D[c]]=size;D[c]=size;
if(H[r]<0)H[r]=L[size]=R[size]=size;
else {
L[size]=H[r];R[size]=R[H[r]];
L[R[H[r]]]=size;R[H[r]]=size;
}
s[c]++;col[size]=c;row[size]=r;size++;
}
void del(int c){//精确覆寫
L[R[c]]=L[c];R[L[c]]=R[c];
FF(i,D,c)FF(j,R,i)U[D[j]]=U[j],D[U[j]]=D[j],--s[col[j]];
}
void add(int c){ //精确覆寫
R[L[c]]=L[R[c]]=c;
FF(i,U,c)FF(j,L,i)++s[col[U[D[j]]=D[U[j]]=j]];
}
bool dfs(int k){//精确覆寫
if(!R[0]){
cnt=k;return 1;
}
int c=R[0];FF(i,R,0)if(s[c]>s[i])c=i;
del(c);
FF(i,D,c){
FF(j,R,i)del(col[j]);
ans[k]=row[i];if(dfs(k+1))return true;
FF(j,L,i)add(col[j]);
}
add(c);
return 0;
}
void remove(int c){//重複覆寫
FF(i,D,c)L[R[i]]=L[i],R[L[i]]=R[i];
}
void resume(int c){//重複覆寫
FF(i,U,c)L[R[i]]=R[L[i]]=i;
}
int A(){//估價函數
int res=0;
memset(vis,0,sizeof(vis));
FF(i,R,0)if(!vis[i]){
res++;vis[i]=1;
FF(j,D,i)FF(k,R,j)vis[col[k]]=1;
}
return res;
}
void dfs(int now,int &ans){//重複覆寫
if(R[0]==0)ans=min(ans,now);
else if(now+A()<ans){
int temp = inf,c;
FF(i,R,0)if(temp>s[i])temp=s[i],c=i;
FF(i,D,c){
remove(i);FF(j,R,i)remove(j);
dfs(now+1,ans);
FF(j,L,i)resume(j);resume(i);
}
}
}
};
DLX AC;
P city[66];
ll dis[66][66], val[3636];
bool check(ll w, int n, int k)
{
AC.init(n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dis[i][j] <= w)
AC.link(i, j);
int ans = inf;
AC.dfs(0, ans);
return ans <= k;
}
int main()
{
int T, n, k, kase = 1;
cin >> T;
while(T--)
{
int cnt = 0;
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
{
scanf("%lld %lld", &city[i].first, &city[i].second);
for(int j = 1; j <= i; j++)
dis[i][j] = dis[j][i] = val[cnt++] = fabs(city[i].first - city[j].first) + fabs(city[i].second - city[j].second);
}
sort(val, val + cnt);
cnt = unique(val, val + cnt) - val;
int l = 0, r = cnt - 1, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(check(val[mid], n, k)) r = mid - 1;
else l = mid + 1;
}
printf("Case #%d: %lld\n", kase++, val[r + 1]);
}
}
代碼(稍加修飾,156ms):
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> P;
const int inf = 0x3f3f3f3f;
int aim;
struct DLX{
const static int maxn=3636;
#define FF(i,A,s) for(int i = A[s];i != s;i = A[i])
int L[maxn],R[maxn],U[maxn],D[maxn];
int size,col[maxn],row[maxn],s[maxn],H[maxn];
bool vis[66];
int ans[maxn],cnt;
void init(int m){
for(int i=0;i<=m;i++){
L[i]=i-1;R[i]=i+1;U[i]=D[i]=i;s[i]=0;
}
memset(H,-1,sizeof(H));
L[0]=m;R[m]=0;size=m+1;
}
void link(int r,int c){
U[size]=c;D[size]=D[c];U[D[c]]=size;D[c]=size;
if(H[r]<0)H[r]=L[size]=R[size]=size;
else {
L[size]=H[r];R[size]=R[H[r]];
L[R[H[r]]]=size;R[H[r]]=size;
}
s[c]++;col[size]=c;row[size]=r;size++;
}
void del(int c){//精确覆寫
L[R[c]]=L[c];R[L[c]]=R[c];
FF(i,D,c)FF(j,R,i)U[D[j]]=U[j],D[U[j]]=D[j],--s[col[j]];
}
void add(int c){ //精确覆寫
R[L[c]]=L[R[c]]=c;
FF(i,U,c)FF(j,L,i)++s[col[U[D[j]]=D[U[j]]=j]];
}
bool dfs(int k){//精确覆寫
if(!R[0]){
cnt=k;return 1;
}
int c=R[0];FF(i,R,0)if(s[c]>s[i])c=i;
del(c);
FF(i,D,c){
FF(j,R,i)del(col[j]);
ans[k]=row[i];if(dfs(k+1))return true;
FF(j,L,i)add(col[j]);
}
add(c);
return 0;
}
void remove(int c){//重複覆寫
FF(i,D,c)L[R[i]]=L[i],R[L[i]]=R[i];
}
void resume(int c){//重複覆寫
FF(i,U,c)L[R[i]]=R[L[i]]=i;
}
int A(){//估價函數
int res=0;
memset(vis,0,sizeof(vis));
FF(i,R,0)if(!vis[i]){
res++;vis[i]=1;
FF(j,D,i)FF(k,R,j)vis[col[k]]=1;
}
return res;
}
bool Dance(int now){//重複覆寫
if(now + A() > aim) return 0;
if(R[0]==0) return now <= aim;
int temp = inf,c;
FF(i,R,0)if(temp>s[i])temp=s[i],c=i;
FF(i,D,c){
remove(i);FF(j,R,i)remove(j);
if(Dance(now+1)) return 1;
FF(j,L,i)resume(j);resume(i);
}
return 0;
}
};
DLX AC;
P city[66];
ll dis[66][66], val[3636];
bool check(ll w, int n, int k)
{
AC.init(n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dis[i][j] <= w)
AC.link(i, j);
aim = k;
return AC.Dance(0);
}
int main()
{
int T, n, k, kase = 1;
cin >> T;
while(T--)
{
int cnt = 0;
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; i++)
{
scanf("%lld %lld", &city[i].first, &city[i].second);
for(int j = 1; j <= i; j++)
dis[i][j] = dis[j][i] = val[cnt++] = fabs(city[i].first - city[j].first) + fabs(city[i].second - city[j].second);
}
sort(val, val + cnt);
cnt = unique(val, val + cnt) - val;
int l = 0, r = cnt - 1, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(check(val[mid], n, k)) r = mid - 1;
else l = mid + 1;
}
printf("Case #%d: %lld\n", kase++, val[r + 1]);
}
}