dancing link

2015年4月1日4,4452

其实感觉就是个搜索的优化

我们只要知道一件事情

就是双向链表中删除一个元素x

l[r[x]]=l[x],r[l[x]]=r[x]

这时候实际上x元素的左右指针没有被改变

所以可以很容易地恢复回来

然后看看代码应该就不难理解了

贴一波代码 hust1017 fzu1686 hdu2295

hust1017 精确覆盖

应该没有更裸的了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define ll long long 
#define inf 1000000000
#define N 2005
#define M 2000005
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,size;
int h[N],s[N],q[N];
int u[M],d[M],L[M],R[M],C[M],X[M];
void del(int c)
{
	L[R[c]]=L[c];R[L[c]]=R[c];
	for(int i=d[c];i!=c;i=d[i])
		for(int j=R[i];j!=i;j=R[j])
			u[d[j]]=u[j],d[u[j]]=d[j],s[C[j]]--;
}
void add(int c)
{
	L[R[c]]=R[L[c]]=c;
	for(int i=u[c];i!=c;i=u[i])
		for(int j=L[i];j!=i;j=L[j])
			u[d[j]]=d[u[j]]=j,s[C[j]]++;
}
void link(int r,int c)
{
	size++;
	X[size]=r;C[size]=c;
	s[c]++;
	d[size]=d[c];u[size]=c;
	u[d[size]]=size;d[u[size]]=size;
	if(h[r]==-1)
		h[r]=L[size]=R[size]=size;
	else 
	{
		R[size]=R[h[r]];L[size]=h[r];
		L[R[size]]=size;R[L[size]]=size;
	}
}
bool dance(int k)
{
	if(R[0]==0)
	{
		printf("%d",k);
		for(int i=1;i<=k;i++)
			printf(" %d",X[q[i]]);
		puts("");
		return 1;
	}
	int mn=inf,c;
	for(int i=R[0];i;i=R[i])
		if(s[i]<mn)mn=s[i],c=i;
	del(c);
	for(int i=d[c];i!=c;i=d[i])
	{
		q[k+1]=i;
		for(int j=R[i];j!=i;j=R[j])del(C[j]);
		if(dance(k+1))return 1;
		for(int j=L[i];j!=i;j=L[j])add(C[j]);
	}
	add(c);
	return 0;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=0;i<=m;i++)
		{
			d[i]=u[i]=i;
			L[i+1]=i;R[i]=i+1;
			s[i]=0;
		}
		R[m]=0;size=m;
		int x,y;
		for(int i=1;i<=n;i++)
		{
			h[i]=-1;
			x=read();
			while(x--)
			{
				y=read();
				link(i,y);
			}
		}
	    if(!dance(0))puts("NO");
	}
	return 0;
}

100

101

102

103

104

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<queue>

#define ll long long

#define inf 1000000000

#define N 2005

#define M 2000005

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,size;

int h[N],s[N],q[N];

int u[M],d[M],L[M],R[M],C[M],X[M];

void del(int c)

{

L[R[c]]=L[c];R[L[c]]=R[c];

for(int i=d[c];i!=c;i=d[i])

for(int j=R[i];j!=i;j=R[j])

u[d[j]]=u[j],d[u[j]]=d[j],s[C[j]]--;

}

void add(int c)

{

L[R[c]]=R[L[c]]=c;

for(int i=u[c];i!=c;i=u[i])

for(int j=L[i];j!=i;j=L[j])

u[d[j]]=d[u[j]]=j,s[C[j]]++;

}

void link(int r,int c)

{

size++;

X[size]=r;C[size]=c;

s[c]++;

d[size]=d[c];u[size]=c;

u[d[size]]=size;d[u[size]]=size;

if(h[r]==-1)

h[r]=L[size]=R[size]=size;

else

{

R[size]=R[h[r]];L[size]=h[r];

L[R[size]]=size;R[L[size]]=size;

}

bool dance(int k)

{

if(R[0]==0)

{

printf("%d",k);

for(int i=1;i<=k;i++)

printf(" %d",X[q[i]]);

puts("");

return 1;

}

int mn=inf,c;

for(int i=R[0];i;i=R[i])

if(s[i]<mn)mn=s[i],c=i;

del(c);

for(int i=d[c];i!=c;i=d[i])

{

q[k+1]=i;

for(int j=R[i];j!=i;j=R[j])del(C[j]);

if(dance(k+1))return 1;

for(int j=L[i];j!=i;j=L[j])add(C[j]);

}

add(c);

return 0;

}

int main()

{

while(scanf("%d%d",&n,&m)!=EOF)

{

for(int i=0;i<=m;i++)

{

d[i]=u[i]=i;

L[i+1]=i;R[i]=i+1;

s[i]=0;

}

R[m]=0;size=m;

int x,y;

for(int i=1;i<=n;i++)

{

h[i]=-1;

x=read();

while(x--)

{

y=read();

link(i,y);

}

if(!dance(0))puts("NO");

}

return 0;

}

fzu1686 裸重复覆盖

实际上重复覆盖仅仅是在精确覆盖基础上略微改动一些

主要是加入一个估价函数，即当前状态至少还需要的步数

从左往右扫每一列，若该列没有元素被选，由于我们不知道选哪个是较优的，于是就同时选取所有元素，代价记为1，显然最后会得出代价的下界

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define ll long long 
#define inf 1000000000
#define N 505
#define M 500005
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,n1,m1,re,size,ans;
int a[25][25];
int u[M],d[M],L[M],R[M],C[M],X[M];
int s[N],h[N];
bool vis[N];
void link(int r,int c)
{
	size++;
	C[size]=c;X[size]=r;
	s[c]++;
	u[size]=c;d[size]=d[c];
	u[d[size]]=size;d[u[size]]=size;
	if(h[r]==-1)
	{
		h[r]=R[size]=L[size]=size;
	}
	else 
	{
		L[size]=h[r];R[size]=R[h[r]];
		L[R[size]]=size;R[L[size]]=size;
	}
}
void build()
{
	for(int i=0;i<=size;i++)
	{
		R[i]=i+1,L[i]=i-1;
		u[i]=d[i]=i;
		s[i]=0;
	}
    memset(h,-1,sizeof(h));
	L[0]=size;R[size]=0;
	for(int i=1;i+n1-1<=n;i++)
		for(int j=1;j+m1-1<=m;j++)
		{
			re++;
			for(int x=i;x<=i+n1-1;x++)
				for(int y=j;y<=j+m1-1;y++)
					if(a[x][y])
						link(re,a[x][y]);
		}
}
void del(int x)
{
	for(int i=d[x];i!=x;i=d[i])
		R[L[i]]=R[i],L[R[i]]=L[i];
}
void add(int x)
{
	for(int i=u[x];i!=x;i=u[i])
		R[L[i]]=L[R[i]]=i;
}
int f()
{
	int ans=0;
	for(int i=R[0];i;i=R[i])
		vis[i]=1;
	for(int i=R[0];i;i=R[i])
		if(vis[i])
		{
			vis[i]=0;ans++;
			for(int j=d[i];j!=i;j=d[j])
				for(int k=R[j];k!=j;k=R[k])
					vis[C[k]]=0;
		}
	return ans;
}
void dance(int k)
{
	if(k+f()>=ans)return;
	if(R[0]==0)
	{
		ans=k;return;
	}
	int c=R[0];
	for(int i=R[0];i;i=R[i])
		if(s[i]<s[c])c=i;
	for(int i=d[c];i!=c;i=d[i])
	{
		del(i);
		for(int j=R[i];j!=i;j=R[j])del(j);
		dance(k+1);
		for(int j=L[i];j!=i;j=L[j])add(j);
		add(i);
	}
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(a,0,sizeof(a));size=re=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				int x=read();
				if(x==1)a[i][j]=++size;
			}
		n1=read();m1=read();
		ans=size;
		build();
		dance(0);
		printf("%d\n",ans);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<queue>

#define ll long long

#define inf 1000000000

#define N 505

#define M 500005

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,n1,m1,re,size,ans;

int a[25][25];

int u[M],d[M],L[M],R[M],C[M],X[M];

int s[N],h[N];

bool vis[N];

void link(int r,int c)

{

size++;

C[size]=c;X[size]=r;

s[c]++;

u[size]=c;d[size]=d[c];

u[d[size]]=size;d[u[size]]=size;

if(h[r]==-1)

{

h[r]=R[size]=L[size]=size;

}

else

{

L[size]=h[r];R[size]=R[h[r]];

L[R[size]]=size;R[L[size]]=size;

}

void build()

{

for(int i=0;i<=size;i++)

{

R[i]=i+1,L[i]=i-1;

u[i]=d[i]=i;

s[i]=0;

}

memset(h,-1,sizeof(h));

L[0]=size;R[size]=0;

for(int i=1;i+n1-1<=n;i++)

for(int j=1;j+m1-1<=m;j++)

{

re++;

for(int x=i;x<=i+n1-1;x++)

for(int y=j;y<=j+m1-1;y++)

if(a[x][y])

link(re,a[x][y]);

}

void del(int x)

{

for(int i=d[x];i!=x;i=d[i])

R[L[i]]=R[i],L[R[i]]=L[i];

}

void add(int x)

{

for(int i=u[x];i!=x;i=u[i])

R[L[i]]=L[R[i]]=i;

}

int f()

{

int ans=0;

for(int i=R[0];i;i=R[i])

vis[i]=1;

for(int i=R[0];i;i=R[i])

if(vis[i])

{

vis[i]=0;ans++;

for(int j=d[i];j!=i;j=d[j])

for(int k=R[j];k!=j;k=R[k])

vis[C[k]]=0;

}

return ans;

}

void dance(int k)

{

if(k+f()>=ans)return;

if(R[0]==0)

{

ans=k;return;

}

int c=R[0];

for(int i=R[0];i;i=R[i])

if(s[i]<s[c])c=i;

for(int i=d[c];i!=c;i=d[i])

{

del(i);

for(int j=R[i];j!=i;j=R[j])del(j);

dance(k+1);

for(int j=L[i];j!=i;j=L[j])add(j);

add(i);

}

int main()

{

while(scanf("%d%d",&n,&m)!=EOF)

{

memset(a,0,sizeof(a));size=re=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

int x=read();

if(x==1)a[i][j]=++size;

}

n1=read();m1=read();

ans=size;

build();

dance(0);

printf("%d\n",ans);

}

return 0;

}

hdu2295

二分以后就是喜闻乐见的重复覆盖

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define ll long long 
#define inf 1000000000
#define N 3005
#define M 2000005
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,n,m,K,size;
int xa[55],ya[55],xb[55],yb[55];
int h[N],s[N];
int u[M],d[M],L[M],R[M],C[M],X[M];
bool vis[N];
double sqr(double x)
{
	return x*x;
}
double dis(int i,int j)
{
	return sqrt(sqr(xa[i]-xb[j])+sqr(ya[i]-yb[j]));
}
void del(int c)
{
	for(int i=d[c];i!=c;i=d[i])
		L[R[i]]=L[i],R[L[i]]=R[i];
}
void add(int c)
{
	for(int i=u[c];i!=c;i=u[i])
		L[R[i]]=R[L[i]]=i;
}
int f()
{
	int ans=0;
	for(int i=R[0];i;i=R[i])vis[i]=1;
	for(int i=R[0];i;i=R[i])
		if(vis[i])
		{
			ans++;vis[i]=0;
			for(int j=d[i];j!=i;j=d[j])
				for(int k=R[j];k!=j;k=R[k])
					vis[C[k]]=0;
		}
	return ans;
}
void link(int r,int c)
{
	size++;
	X[size]=r;C[size]=c;s[c]++;
	d[size]=d[c];u[size]=c;
	u[d[size]]=size;d[u[size]]=size;
	if(h[r]==-1)
		h[r]=L[size]=R[size]=size;
	else 
	{
		R[size]=R[h[r]];L[size]=h[r];
		L[R[size]]=size;R[L[size]]=size;
	}
}
bool dance(int k)
{
	if(R[0]==0)
		return 1;
	if(k+f()>K)return 0;
	int c=R[0];
	for(int i=c;i;i=R[i])
		if(s[i]<s[c])c=i;
	for(int i=d[c];i!=c;i=d[i])
	{
		del(i);
		for(int j=R[i];j!=i;j=R[j])del(j);
		if(dance(k+1))return 1;
		for(int j=L[i];j!=i;j=L[j])add(j);
		add(i);
	}
	return 0;
}
void build(double mid)
{
	for(int i=0;i<=n;i++)
	{
		L[i+1]=i;R[i]=i+1;
		u[i]=d[i]=i;
		s[i]=0;
	}
	R[n]=0;L[0]=n;
	size=n;
	for(int i=1;i<=m;i++)h[i]=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(dis(i,j)<=mid)link(j,i);
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();m=read();K=read();
		for(int i=1;i<=n;i++)
			xa[i]=read(),ya[i]=read();
		for(int i=1;i<=m;i++)
			xb[i]=read(),yb[i]=read();
		double l=0,r=1e8;
		for(int i=1;i<=60;i++)
		{
			double mid=(l+r)/2;
			build(mid);
			if(dance(0))r=mid;
			else l=mid;
		}
		printf("%.6lf\n",l);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<queue>

#define ll long long

#define inf 1000000000

#define N 3005

#define M 2000005

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T,n,m,K,size;

int xa[55],ya[55],xb[55],yb[55];

int h[N],s[N];

int u[M],d[M],L[M],R[M],C[M],X[M];

bool vis[N];

double sqr(double x)

{

return x*x;

}

double dis(int i,int j)

{

return sqrt(sqr(xa[i]-xb[j])+sqr(ya[i]-yb[j]));

}

void del(int c)

{

for(int i=d[c];i!=c;i=d[i])

L[R[i]]=L[i],R[L[i]]=R[i];

}

void add(int c)

{

for(int i=u[c];i!=c;i=u[i])

L[R[i]]=R[L[i]]=i;

}

int f()

{

int ans=0;

for(int i=R[0];i;i=R[i])vis[i]=1;

for(int i=R[0];i;i=R[i])

if(vis[i])

{

ans++;vis[i]=0;

for(int j=d[i];j!=i;j=d[j])

for(int k=R[j];k!=j;k=R[k])

vis[C[k]]=0;

}

return ans;

}

void link(int r,int c)

{

size++;

X[size]=r;C[size]=c;s[c]++;

d[size]=d[c];u[size]=c;

u[d[size]]=size;d[u[size]]=size;

if(h[r]==-1)

h[r]=L[size]=R[size]=size;

else

{

R[size]=R[h[r]];L[size]=h[r];

L[R[size]]=size;R[L[size]]=size;

}

bool dance(int k)

{

if(R[0]==0)

return 1;

if(k+f()>K)return 0;

int c=R[0];

for(int i=c;i;i=R[i])

if(s[i]<s[c])c=i;

for(int i=d[c];i!=c;i=d[i])

{

del(i);

for(int j=R[i];j!=i;j=R[j])del(j);

if(dance(k+1))return 1;

for(int j=L[i];j!=i;j=L[j])add(j);

add(i);

}

return 0;

}

void build(double mid)

{

for(int i=0;i<=n;i++)

{

L[i+1]=i;R[i]=i+1;

u[i]=d[i]=i;

s[i]=0;

}

R[n]=0;L[0]=n;

size=n;

for(int i=1;i<=m;i++)h[i]=-1;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

if(dis(i,j)<=mid)link(j,i);

}

int main()

{

T=read();

while(T--)

{

n=read();m=read();K=read();

for(int i=1;i<=n;i++)

xa[i]=read(),ya[i]=read();

for(int i=1;i<=m;i++)

xb[i]=read(),yb[i]=read();

double l=0,r=1e8;

for(int i=1;i<=60;i++)

{

double mid=(l+r)/2;

build(mid);

if(dance(0))r=mid;

else l=mid;

}

printf("%.6lf\n",l);

}

return 0;

}

« 「BC35」DZY Loves Balls 「CF534X」Codeforces Round #298 (Div. 2) »

吴钰晗

黄学长您在发博文的时候我们是不是进不了网站？

hzwer

不是吧。。可能是我服务器太烂了

hzwer.com _ Home | http://hzwer.com

dancing link

分类目录

热门文章

Myfriends

近期评论