关于舞蹈链速度
查看原帖
关于舞蹈链速度
289056
北射天狼楼主2023/10/29 15:45
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,请问一下这其中是什么原因啊?

2023/10/29 15:45
加载中...