社区讨论

关于舞蹈链速度

P4929【模板】舞蹈链(DLX)参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lob64h6c
此快照首次捕获于
2023/10/29 15:47
2 年前
此快照最后确认于
2023/11/02 10:52
2 年前
查看原帖
CPP
bool dance(int x){
		if (!R[0]){
			ans = x;
			return 1;
		}
		int c = R[0];
		for (int i=R[0];i != 0;i = R[i])
		    if (siz[i] < siz[c])
		        c = i;//less 1;
	    remove(c);
	    //choose a column with the less 1
	    for (int i = D[c];i != c;i = D[i]){
	    	stk[x] = row[i];
	    	//choose a row with the less 1
	    	//delete the row and the col with 1
	    	for (int j = R[i];j != i;j = R[j])
	    	    remove(col[j]);
	    	if (dance(x + 1))
	    	    return 1;
	    	for (int j = L[i];j != i;j = L[j])
	    	    recover(col[j]);
		}
		recover(c);
		return 0;
	}
如上是本题的搜索函数,也就是先选择一列,把这列干掉。题解是选择 11 最少的一列。
但是选择哪一列对速度快慢有影响吗?我改了改代码,如果换成选择 11 最多的列会直接 TLE 10pts,请问一下这其中是什么原因啊?

回复

5 条回复,欢迎继续交流。

正在加载回复...