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