对于数独问题
const int N=; //3*3数独
const int MaxN=N*N*N+; // 一格能填9个数 9*9格
const int MaxM=N*N*+; // 9*9*4=(9+9+9)*9+9*9 (9+9+9)是9行 9列 9格 *9是9个数 9*9是81个格子
const int maxnode=MaxN*+MaxM+;
char g[MaxN];
struct DLX
{
int n, m, size;
int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode];
int H[MaxN], S[MaxM]; // S: 各列节点数
int ansd, ans[MaxN];
void init(int _n, int _m)
{
n=_n;
m=_m;
for(int i=; i<=m; i++)
{
S[i]=; //每一列元素个数
U[i]=D[i]=i;//上下指针
L[i]=i-; //←
R[i]=i+; //→
}
R[m]=; //循环 最后一个指向第一个
L[]=m; //第一个往前指向最后一个
size=m; // 节点总数
for(int i=; i<=n; i++)
H[i]=-; //头指针
}
void Link(int r, int c)
{
S[Col[++size]=c]++;
Row[size]=r;
D[size]=D[c];
U[D[c]]=size;
U[size]=c;
D[c]=size;
if(H[r]<)
H[r]=L[size]=R[size]=size;
else
{
R[size]=R[H[r]];
L[R[H[r]]]=size;
L[size]=H[r];
R[H[r]]=size;
}
}
void remove(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[Col[j]]--;
}
}
void resume(int c)
{
for(int i=U[c]; i!=c; i=U[i])
for(int j=L[i]; j!=i; j=L[j])
S[Col[U[D[j]]=D[U[j]]=j]]++;
L[R[c]]=R[L[c]]=c;
}
bool Dance(int d)
{
if(R[]==)
{
for(int i=;i<d;i++)
g[(ans[i]-)/N]=(ans[i]-)%N+'A';
for(int i=;i<N;i++)
{
for(int j=;j<N;j++)
printf("%c", g[i*N+j]);
printf("\n");
}
printf("\n");
return true;
}
int c=R[];
for(int i=R[]; i!=; i=R[i])
if(S[i]<S[c])
c=i;
remove(c);
for(int i=D[c]; i!=c; i=D[i])
{
ans[d]=Row[i];
for(int j=R[i]; j!=i; j=R[j])
remove(Col[j]);
if(Dance(d+))
return true;
for(int j=L[i]; j!=i; j=L[j])
resume(Col[j]);
}
resume(c);
return false;
}
} dlx; void palce(int &r, int &c1, int &c2, int &c3, int &c4, int i, int j, int k)
{
r=(i*N+j)*N+k; // 第几行
c1=i*N+j+; // 第几个格子
c2=N*N+i*N+k; // 第i行上的k
c3=N*N*+j*N+k; // 第j列上的k
c4=N*N*+((i/)*+(j/))*N+k; // 某宫中的k;
}
char s[];
int main()
{
while(~scanf("%s", g))
{
for(int i=;i<;i++)
{
scanf("%s", s);
memcpy(g+*i, s, );
}
dlx.init(N*N*N, *N*N);
for(int i=; i<N; i++)
for(int j=; j<N; j++)
for(int k=; k<=; k++)
if(g[i*N+j]=='-' || g[i*N+j]==k+'A'-)
{
int r, c1, c2, c3, c4;
palce(r, c1, c2, c3, c4, i, j, k);
dlx.Link(r, c1);
dlx.Link(r, c2);
dlx.Link(r, c3);
dlx.Link(r, c4);
}
dlx.Dance();
}
return ;
}
POJ 3076
( 以上的模板只能做唯一解的数独)
判读多解要做dfs
对于可重复覆盖
#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#pragma comment(linker, "/STACK:1024000000,1024000000")
//LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans%mod;}
inline int read(){char ch=' ';int ans=;while(ch<'' || ch>'')ch=getchar();while(ch<='' && ch>=''){ans=ans*+ch-'';ch=getchar();}return ans;}
inline void print(LL x){printf(LLD, x);puts("");}
//inline void read(LL &ret){char c;int sgn;LL bit=0.1;if(c=getchar(),c==EOF) return ;while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');if(c==' '||c=='\n'){ ret*=sgn; return ; }while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;ret*=sgn;} const int maxnode=;
const int MaxN=;
const int MaxM=;
int K;
struct DLX
{
int n, m, size;
int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode];
int H[MaxN], S[MaxM]; // S: 各列节点数
int ans[MaxN];
void init(int _n, int _m)
{
n=_n;
m=_m;
for(int i=; i<=m; i++)
{
S[i]=; //每一列元素个数
U[i]=D[i]=i;//上下指针
L[i]=i-; //←
R[i]=i+; //→
}
R[m]=; //循环 最后一个指向第一个
L[]=m; //第一个往前指向最后一个
size=m; // 节点总数
for(int i=; i<=n; i++)
H[i]=-; //头指针
}
void Link(int r, int c)
{
S[Col[++size]=c]++;
Row[size]=r;
D[size]=D[c];
U[D[c]]=size;
U[size]=c;
D[c]=size;
if(H[r]<)
H[r]=L[size]=R[size]=size;
else
{
R[size]=R[H[r]];
L[R[H[r]]]=size;
L[size]=H[r];
R[H[r]]=size;
}
}
void remove(int c)
{
for(int i=D[c]; i!=c; i=D[i])
L[R[i]]=L[i], R[L[i]]=R[i];
}
void resume(int c)
{
for(int i=U[c]; i!=c; i=U[i])
L[R[i]]=R[L[i]]=i;
}
bool v[maxnode];
int f()
{
int ret=;
for(int c=R[];c!=;c=R[c])
v[c]=;
for(int c=R[];c!=;c=R[c])
if(v[c])
{
ret++;
v[c]=;
for(int i=D[c];i!=c;i=D[i])
for(int j=R[i];j!=i;j=R[j])
v[Col[j]]=;
}
return ret;
}
bool Dance(int d)
{
if(d+f()>K)
return false;
if(R[]==)
return d<=K;
int c=R[];
for(int i=R[]; i!=; i=R[i])
if(S[i]<S[c])
c=i;
for(int i=D[c]; i!=c; i=D[i])
{
remove(i);
for(int j=R[i]; j!=i; j=R[j])
remove(j);
if(Dance(d+))
return true;
for(int j=L[i]; j!=i; j=L[j])
resume(j);
resume(i);
}
return false;
}
} dlx;
struct node
{
int x, y;
}city[MaxM];
LL dis(node a, node b)
{
return (LL)abs(a.x-b.x)+(LL)abs(a.y-b.y);
}
int main()
{
int t, ca=;
t=read();
while(t--)
{
int n=read();
K=read();
for(int i=;i<n;i++)
scanf("%d%d", &city[i].x, &city[i].y);
LL l=, r=100000000000LL, ans=;
while(l<=r)
{
LL mid=(l+r)>>;
dlx.init(n, n);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
if(dis(city[i], city[j])<=mid)
dlx.Link(i+, j+);
if(dlx.Dance())
{
r=mid-;
ans=mid;
}
else
l=mid+;
}
printf("Case #%d: ", ca++);
print(ans);
}
return ;
}
HDUOJ 5046
两篇资料：
http://wenku.baidu.com/view/b3f6fa868762caaedd33d47a.html
http://wenku.baidu.com/view/4ab7bd00a6c30c2259019eae.html?from=rec&pos=0&weight=31&lastweight=5&count=5