精确覆盖DLX算法模板
2024-08-28 20:05:39
代码
struct DLX
{
int n,id;
int L[maxn],R[maxn],U[maxn],D[maxn];
int C[maxn],S[maxn],loc[maxn][];
void init(int nn=) //传列长
{
n=nn;
for(int i=;i<=n;i++) U[i]=D[i]=i,L[i]=i-,R[i]=i+;
L[]=n; R[n]=;
id=n;
memset(S,,sizeof(S));
}
void AddRow(int x,int col,int A[]) //传入参数是行标号,列长,列数组
{
bool has=false;
int first=id+;
for(int y=;y<=col;y++)
{
if(A[y]==) continue;
has=true;
++id;
L[id]=id-; R[id]=id+;
D[id]=y; U[id]=U[y];
D[U[y]]=id; U[y]=id;
loc[id][]=x,loc[id][]=y;
C[id]=y; S[y]++;
}
if(!has) return;
R[id]=first; L[first]=id;
}
void Remove(int Size)
{
for(int j=D[Size];j!=Size;j=D[j])//将左右两边连接
L[R[j]]=L[j],R[L[j]]=R[j];
}
void Resume(int Size)
{
for(int j=U[Size];j!=Size;j=U[j])//恢复
L[R[j]]=R[L[j]]=j;
}
bool vis[ms];//标记行是否访问过
int h() //启发式函数
{
int ret=;
int i,j,k;
memset(vis,,sizeof(vis));
for(i=R[];i;i=R[i])
{
if(vis[i]) continue;
ret++;
for(j=D[i];j!=i;j=D[j]) //所有关联的标记了
for(k=R[j];k!=j;k=R[k]) vis[C[k]]=;
}
return ret;
}
void dfs(int step)
{
if(step+h()>=ans) return;
if(R[]==){ ans=min(ans,step); return; }
int Min=INF,c=-;
for(int i=R[];i;i=R[i]) if(Min>S[i]){ Min=S[i]; 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);
dfs(step+);
for(int j=L[i];j!=i;j=L[j]) Resume(j);
Resume(i);
}
return;
}
}dlx;
最新文章
- Neo4j批量插入(Batch Insertion)
- 在ScrollView下加入的组件,不能自动扩展到屏幕高度
- 腾讯优测-优社区干货精选 | &#160;那些年,我们在Android机型适配上遇到的坑之Camera拍照时快门咔嚓声
- 性能测试一般过程与LR性能测试过程
- 第二十章、启动流程、模块管理与 Loader
- Google+ 技巧四则
- 后缀自动机(SAM) :SPOJ LCS - Longest Common Substring
- Notepad++编译c++时使用的代码
- XML数组和对象,反之亦然
- 深度神经网络(DNN)的正则化
- python掉微信api
- STL -->; list用法
- Spring Boot分布式系统实践【基础模块构建3.3】注解轻松实现操作日志记录
- Node.js、npm、vue-cli 的安装配置环境变量
- AJAX html 传输json字符串&;&;巧妙运用eval()来解析返回的JSON字符串
- 【C#】详解C#事件
- MySQL 如何创建索引?怎么优化?
- python opencv3 cornerHarris 角点检测
- Azure 经典模式中虚拟机证书指纹的生成和作用
- vuex 定义