[ZOJ3209 Treasure Map] DLX解决精确覆盖问题中我的一个错误>.<

HHGG出的题T_T。

本身题目没啥好说的。很容易转化为精确覆盖。

但是我之前的DLX模板超时了。

好吧，那个在HUST1017上跑了4S的模板果然是不能用的。

然后，我照着hh(the small one)的模板YY出意思然后写了一个。HUST上…还是跑了1500+MS.这题还是TLE。

我记得之前那篇CLJ留言鄙视说暴力开指针都600+MS…

我再看了好多遍，觉得和hh的没啥区别嘛…为啥人家说200+MS

好多遍好多遍以后…我突然看到了一个不一样。

hh的：

    回溯部分：

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

    resume函数部分：

     for (int i=U[col];i!=col;i=U[i])

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

 

我的

    回溯部分：

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

    resume函数部分

     for (int i=D[col];i!=col;i=D[i])

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

 

 然而，我的其实犯了一个错误。

Dancing Link其实必须按照删除的先后顺序，依次恢复的。

比如删除的顺序是i,j，恢复的顺序就应当是j,i。举个例子就能知道原因

HUST的1017上

在for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);这种方式下。无论resume函数里随便用ULDR都可以240MS左右AC。

而for (int j=R[i];j!=i;j=R[j]) resume(Col[j]);这种方式下。resume函数里如果用D可以1500MS AC。然后，如果是U的话就runtime error了。可见这种方式确实是错误的>.<

恩，终于搞了一个能用的精确覆盖模板了。

以后把mat和Num建好，一刷就好了

需要注意的是代码里，为了方便和速度，把二维点映射到一维上了。

http://ideone.com/2M7T4