舞蹈链解精确覆盖问题

原创
10/28 00:17
阅读数 22

dfs解的话会遇到一个问题:

比如答案是前2-10行和第12行, 那么由于第一和第十一行会导致冲突了, 导致dfs必须走完2-10行的排列才能判断出错误, 有太多无效判断了

https://www.cnblogs.com/grenet/p/3145800.html

https://blog.csdn.net/just_sort/article/details/52203094?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-8.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-8.channel_param

 

懒得写了,就找了一个舞蹈链的模板

需要注意, 舞蹈链中的下标都是由1开始的

首先把01数组转成稀疏矩阵, 然后用c++求解该精确匹配问题, 最后使用得到的答案反解出数组

 

可以考虑使用wasm和worker在js端加速

成功反解出来了

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部