整了一天的跳舞鏈，資料可以在網上搜到
http://sqybi.com/works/dlxcn/驚訝于它做深搜的時候可以達到如此強勁的剪枝
下午的時候不看網上的模板自己寫了一個，自認為是比模板少了一個for循環，但是寫好后才發現沒有模板的啟發式搜索的效率，就這樣活生生的TLE了，浪費了我好幾個小時啊~~%>_<%~~
晚上只好寫用模板的方法，寫了一個后瞬間過了，感覺難度也不過爾爾
但這個舞蹈鏈可是容易解答卻很難看出的主，構造舞蹈鏈還是關鍵
獻上我的模板~~
最簡單的舞蹈鏈，效率僅比hhanger差，可以跑240MS,不過后來我測出了一些數據的結構，暴力優化到了124MS，哈哈哈(得意一下)~~~
http://acm.hust.edu.cn/thanks/problem.php?id=1017(精確覆蓋問題)
void remove(int &c) {
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i = D[c]; i != c ; i = D[i]) {
for(int j = R[i]; j != i ; j = R[j]) {
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[Col[j]];
}
}
}
void resume(int &c) {
for(int i = U[c];i != c;i = U[i]) {
for(int j = L[i]; j != i ; j = L[j]) {
++S[Col[j]];
U[D[j]] = j;
D[U[j]] = j;
}
}
L[R[c]] = c;
R[L[c]] = c;
}
bool dfs() {
if(R[0] == 0) {
return true;
}
int i , j;
int idx,minnum = 999999;
for(i = R[0];i != 0 ; i = R[i]) {
if(S[i] < minnum) {
minnum = S[i];
idx = i;
}
}
remove(idx);
for(i = D[idx]; i != idx; i = D[i]) {
ans[deep++] = Row[i];
for(j = R[i]; j != i ; j = R[j]) {
remove(Col[j]);
}
if(dfs()) {
return true;
}
deep --;
for(j = L[i]; j != i ; j = L[j]) {
resume(Col[j]);
}
}
resume(idx);
return false;
}
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3209(精確覆蓋問題)
浙大的這道省賽題其實就是完美覆蓋的轉化~把每一格都分開來，要求就是選N個方塊把圖完美覆蓋全部搜完然后最小的個數
思路：行方塊，列單位小格子，矩陣中1是方塊所能覆蓋的小格子
http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1507
(重復覆蓋問題) 重復覆蓋的模板題
獻上模板
void remove(int &c) {
for(int i = D[c]; i != c ; i = D[i]) {
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void resume(int &c) {
for(int i = U[c]; i != c ; i = U[i]) {
L[R[i]] = i;
R[L[i]] = i;
}
}
int h() {
bool hash[51];
memset(hash,false,sizeof(hash));
int ret = 0;
for(int c = R[0]; c != 0 ; c = R[c]) {
if(!hash[c]) {
ret ++;
hash[c] = true;
for(int i = D[c] ; i != c ; i = D[i]) {
for(int j = R[i] ; j != i ; j = R[j]) {
hash[Col[j]] = true;
}
}
}
}
return ret;
}
bool dfs(int deep,int lim) {
if(deep + h() > lim) {
return false;
}
if(R[0] == 0) {
return true;
}
int idx , i , j , minnum = 99999;
for(i = R[0] ; i != 0 ; i = R[i]) {
if(S[i] < minnum) {
minnum = S[i];
idx = i;
}
}
for(i = D[idx]; i != idx; i = D[i]) {
remove(i);
for(j = R[i]; j != i ; j = R[j]) {
remove(j);
}
if(dfs(deep+1,lim)) {
return true;
}
for(j = L[i]; j != i ; j = L[j]) {
resume(j);
}
resume(i);
}
return false;
}
http://acm.tju.edu.cn/acm/showp3219.html http://acm.hdu.edu.cn/showproblem.php?pid=2295(重復覆蓋問題)
這題無法轉化成完美覆蓋，所以remove和resume的時候要變化一下，但是這樣還是會超時我看了標程才算AC。唉。。
主要是里邊的一個A*的h函數是在是太犀利了，一下從TLE到了46MS。。。。剪枝還是非常重要的
思路：行是雷達，列是城市，矩陣中1是雷達覆蓋城市
http://acm.fzu.edu.cn/problem.php?pid=1686 (重復覆蓋問題)
這道題也同上道一樣是："在0-1矩陣中選取最少的行，使得每一列最少有一個1" 這個模型
所以和上一道建表一樣建好之后套上模板就AC了~
思路：行是枚舉在每個位子放魔法，列式怪物個數(最好給怪物標記個id)，矩陣中的1是在這個地方放魔法是否能達到目標怪物
http://www.spoj.pl/problems/NQUEEN/(重復覆蓋問題)
N皇后問題，打的時候沒能想到怎么轉化成精確覆蓋，只是用了dancing links的思想，傻傻的花了一個晚上完成了一個超級復雜的米字型鏈表(重復覆蓋)，開始的時候啟發式函數S沒有更新，導致沒有發揮效用，結果本例30個0的數據都跑不出來，還以為是想法出錯了，睡覺前在床上想到，改了一下，效率呈指數級增長，50個0的瞬間跑出來，在state里排到第一，哈哈
(精確覆蓋問題)
今天CH教我怎么將之轉化成十字鏈表的精確覆蓋，但是矩陣是(n*n)*(6*n-2)比米字型鏈表n*n的大了好多倍，交了一下，跑了1s，效率不如米字型的
其思路是：行是格子數n*n,列是(行+列+正逆對角線)，矩陣中的1是放在各自上所占得行，列，對角線
不需要全部搜完，只要初始皇后+dfs的深度達到n(放了n個皇后)就return true
http://acm.hdu.edu.cn/showproblem.php?pid=2828
(精確覆蓋問題)
這題惡化N皇后一樣可以轉化成多種覆蓋。我是精確覆蓋，列是n+m只要精確前n個就夠了
(重復覆蓋問題)
還可以轉化成不精確，那么列就是n
當然，此題出題人的意圖是二分匹配。。。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=31http://acm.pku.edu.cn/JudgeOnline/problem?id=1084(重復覆蓋問題)
這題要不和我說是dancing links 我還真看不出來
此題建表超煩，雖看出來但是建表就花了我一個半小時，還迫我使用上行的頭節點，以前我只是用列的頭節點，努力了很久，過了sample就AC了，煩就煩在建表上
思路：行是火柴棒數，列是完美時能構成的矩陣數目，矩陣中的1是列矩陣是否包含行火柴
http://acm.pku.edu.cn/JudgeOnline/problem?id=3074http://acm.pku.edu.cn/JudgeOnline/problem?id=3076http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3038(精確覆蓋問題)
經典的數獨，看了論文才明白怎么覆蓋，9*9*9的行 (9+9+9)*9+9*9的列
思路：行是81個小格*每個格子的9個可能數字，列是81個小格+9行9列9小塊的9個數字
每列確切的有4個1
開始讀入的時候吧確定的數字的頭上的1刪掉可以很大的提高效率
http://acm.hdu.edu.cn/showproblem.php?pid=2518
超爽的dancing links
這題所有的方塊可以旋轉，這點超煩~
我差點就人肉代碼了，枚舉所有狀態，不過最后我還是修改成不人肉的辦法
只有幾組答案，用dancing links暴力跑出所有組合后然后打表，嘿嘿，我就是這么猥瑣的過的
72*所有擺放數~
思路：60個格子加12個方塊作為列，所有擺放的方案數作為行
好了，A光上述題目dancing links的學習也告一段落，這個舞蹈是在是優美，以后出題一定要譜一曲經典的舞蹈~~
2009.9.6
發現dancing links還能做
最大團http://acm.hdu.edu.cn/showproblem.php?pid=1530轉化成補圖后再建表。。。不過效率很低，跑了6000+MS，全部搜完找一個最大的，還沒有更優的辦法優化，嘗試過二分再寫個h函數未果。。。
10.15
http://acm.hdu.edu.cn/showproblem.php?pid=3156和雷達類似，不過放radar的點要求出來，也是先二分枚舉半徑，然后利用兩個點和半徑確定一個圓心C(n,2)，可以證明如果放其他地方一定沒這個圓心優
posted on 2009-07-10 01:17
shǎ崽 閱讀(11534)
評論(13) 編輯 收藏 引用