0x21 樹與圖的遍歷

樹與圖的深度優(yōu)先遍歷

深度優(yōu)先遍歷，就是在每個點\(x\)上面的的多條分支時，任意選擇一條邊走下去，執(zhí)行遞歸，直到回溯到點x后再走其他的邊

int head[N]; bool v[N]; struct edge {int v , next; }e[N];inline void dfs( int x ) {v[x] = 1;for( register int i = head[x] ; i ; i = e[i].next){register int y = e[i].next;if( v[y] ) continue;dfs( y ) ;}return ; }

樹的DFS序

一般來說，我們在對樹的進行深度優(yōu)先時，對于每個節(jié)點，在剛進入遞歸時和回溯前各記錄一次該點的編號，最后會產(chǎn)生一個長度為\(2N\)的序列，就成為該樹的\(DFS\)序

\(DFS\)序的特點時：每個節(jié)點的\(x\)的編號在序列中恰好出現(xiàn)兩次。設(shè)這兩次出現(xiàn)的位置時\(L[x]\),\(R[x]\)，那么閉區(qū)間\([L[x],R[x]]\)就是以\(x\)為根的子樹的\(DFS\)序

inline void dfs( int x ) {a[ ++ tot ] = x; // a儲存的是DFS序v[ x ] = 1;for( register int i = head[x] ; i ; i = e[i].next ){register int y = e[i].v;if( v[y] ) continue;dfs( y );}a[ ++ tot ] = x;return ; }

樹的深度

樹中各個節(jié)點的深度是一種自頂向下的統(tǒng)計信息

起初，我們已知根節(jié)點深度是\(0\).若節(jié)點\(x\)的深度為\(d[x]\),則它的節(jié)點\(y\)的深度就是\(d[y] = d[x] + 1\)

inline void dfs( int x ) {v[ x ] = 1;for( register int i = head[ x ] ; i ; i = e[i].next ){register int y = e[i].v;if( v[ y ] ) continue;d[ y ] = d[ x ] + 1; // d[]就是深度dfs( y );}return ; }

樹的重心

對于一個節(jié)點\(x\)，如果我們把它從樹中刪除，呢么原來的一顆樹可能會被分割成若干個樹。設(shè)\(max\_part(x)\)表示在刪除節(jié)點\(x\)后產(chǎn)生子樹中最大的一顆的大小。使\(max\_part(p)\)最下的\(p\)就是樹的重心

inline void dfs( int x ) {v[ x ] = 1 , size[ x ] = 1;//size 表示x的子樹大小 register int max_part = 0; // 記錄刪掉x后最大一顆子樹的大小 for( register int i = head[ x ] ; i ; i = e[i].next ){register int y = e[i].v;if( v[y] ) continue;dfs( y );size[x] += size[y];} max_part = max ( max_part , n - size[x] );if( max_part < ans ) //全局變量ans記錄重心對應(yīng)的max_part { ans = max_part;pos = x;//pos 重心 }return ; }

圖的聯(lián)通塊劃分

若在一個無向圖中的一個子圖中任意兩個點之間都存在一條路徑（可以相互到達），并且這個子圖是“極大的”（不能在擴展），則稱該子圖是原圖的一個聯(lián)通塊

如下代碼所示，cnt是聯(lián)通塊的個數(shù)，v記錄的是每一個點屬于哪一個聯(lián)通塊

inline void dfs( int x ) {v[ x ] = cnt;for( register int i = head[x] ; i ; i = e[i].next ) {register int y = e[i].v;if( v[y] ) continue;dfs(y);}return ; }for( register int i = 1 ; i < = n ; i ++ ) {if( v[i] ) continue;cnt ++ ;dfs( i ); }

圖的廣度優(yōu)先搜索遍歷

樹與圖的廣度優(yōu)先遍歷是利用一個隊列來實現(xiàn)的

queue< int > q;inline void bfs() {q.push( 1 ) , d[1] = 1;while( !q.empty() ){register int x = q.front(); q.pop();for( register int i = head[ x ] ; i ; i = e[i].next ){register int y = e[i].v;if( d[y] ) continue;d[y] = d[x] + 1;q.push(y);} }return ; }

上面的代碼中，我們在廣度優(yōu)先搜索中順便求了個樹的深度\(d\)

AcWing 164. 可達性統(tǒng)計

這道題的題意很簡單，但是如果直接裸的計算會超時，所以要用拓?fù)湫?/p>

首先求拓?fù)湫?#xff0c;因為拓?fù)湫蛑械拿恳粋€點都時由前面的點到的所以我們反過來從最后一個點開始

假設(shè)我們已經(jīng)求得了\(x\)后面每一個點的所能到達的點，呢么我們對所有以x為起點的邊所到達的點所能到達的點取并集就是\(x\)所等到達的所有的點

然后如果們要儲存每個點所到達的點，如果我們用二維數(shù)組來存，會爆空間，所以為了節(jié)約空間可以用<bitset>來存

#include <bits/stdc++.h> using namespace std;const int N = 30010; int n , m , head[N] , d[N] , a[N] , tot , cnt ; bitset< N > f[N];struct edge {int v , next; }e[N];inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 1 ) + ( x << 3 ) + ch - '0';ch = getchar();}return x; }inline void addedge( int u , int v ) {e[ ++ tot ].v = v , e[ tot ].next = head[u] , head[u] = tot;d[ v ] ++; }inline void topsort() {queue< int > q;for( register int i = 1 ; i <= n ; i ++ ){if( !d[i] ) q.push( i );}while( !q.empty() ){register int x = q.front(); q.pop();a[ ++ cnt ] = x;for( register int i = head[x] ; i ; i = e[i].next ){register int y = e[i].v;if( -- d[y] == 0 ) q.push( y );}}return ; }int main() {n = read() , m = read();for( register int i = 1 ; i <= m ; i ++ ){register int a = read() , b = read();addedge( a , b );}topsort();for( register int i = cnt , j = a[i] ; i ; i -- , j = a[i] ){f[j][j] = 1;for( register int k = head[j] ; k ; k = e[k].next ) f[j] |= f[ e[k].v ];}for( register int i = 1 ; i <= n ; i ++ ) printf( "%d\n" , f[i].count() );return 0; }

0x22 深度優(yōu)先搜索

深度優(yōu)先搜索算法\((Depth-First-Search)\)是一種用于遍歷或搜索樹或圖的算法

沿著樹的深度遍歷樹的節(jié)點，盡可能深的搜索樹的分支。當(dāng)節(jié)點\(v\)的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復(fù)以上過程，整個進程反復(fù)進行直到所有節(jié)點都被訪問為止。

AcWing 165. 小貓爬山

這道題時dfs最基礎(chǔ)的題目了

我們只需設(shè)計搜索的狀態(tài)這道題就可以輕易的寫出來

我們設(shè)(x,y)是搜索的狀態(tài)即前x個小貓用了y個纜車

我們要轉(zhuǎn)移的情況只有兩種

小貓上前y輛纜車

小貓上y+1輛纜車（新開一輛）

所以我們只要枚舉就好

然后就是如何優(yōu)化算法

首先假如我們已經(jīng)得到一個解pay,若此時的大于pay則不可能會更優(yōu)，所以可以自己而回溯

然后我們把小貓從大到小排序可以排除很多不可能是結(jié)果的情況

#include <bits/stdc++.h> using namespace std;const int N = 20; int n , w , c[N] , f[N], pay = N;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();} return x; }inline void dfs( int x , int y ) {if( x > n ){pay = min( pay , y );return ;}if( y > pay ) return ;for( register int i = 1 ; i <= y ; i ++ ){if( f[i] + c[x] > w ) continue;f[i] += c[x];dfs( x + 1 , y );f[i] -= c[x];}y ++;f[y] += c[x];dfs( x + 1 , y );f[y] = 0;return ; }inline bool cmp( int x , int y ) { return x > y; }int main() {n = read() , w = read();for( register int i = 1 ; i <= n ; i ++ ) c[i] = read();sort( c + 1 , c + 1 + n , cmp );dfs( 1 , 0 );cout << pay << endl;return 0; }

AcWing 166. 數(shù)獨

這是一道經(jīng)典的搜索題，不過是數(shù)據(jù)加強過的版本，所有直接搜索會T

必須要進行一些優(yōu)化

首先我們想自己玩數(shù)獨的時候是怎么玩的

肯定是首先填可能的結(jié)果最少的格子，在也是這道題優(yōu)化的核心

如何快速的確定每個格子的情況？

const int n = 9; int row[n] , col[n] , cell[3][3]; // row[] 表示行 col表示列 cell[][] 表示格子

我們用一個九位二進制數(shù)來表示某一行、某一列、或某一個中可以填入的數(shù)，其中1表示可以填，0表示不能填

對于\((x,y)\)這個點我們只需\(row[x] \bigcap col[y] \bigcap cell[\frac{x}{3}][\frac{y}{3}]\)就可以知道這個點可以填入數(shù)字的集合然后用lowbit()把每一位取出來即可

而在二進制中的交集就是$& $操作，所以取交集的函數(shù)就是

inline int get( int x , int y ) {return row[ x ] & col[ y ] & cell[ x / 3 ][ y / 3]; }

還有什么優(yōu)化呢，lowbit()的時間復(fù)雜度是\(O(log(n))\)我們可以通過預(yù)處理把一些操作變成\(O(1)\)的

首先每次lowbit()得到的并不是最后一個一定位置而是一個二進制數(shù)，可以用這個maps[]，\(O(1)\)查詢最后一為的具體位置

for( register int i = 0 ; i < n ; i ++ ) maps[ 1 << i ] = i;

其次對于每個二進制數(shù)中有多少個\(1\)的查詢也是很慢的，可以用這個ones[]，\(O(1)\)查詢一個二進制數(shù)中有多少個\(1\)

for( register int i = 0 , s = 0 ; i < 1 << n ; i ++ , s = 0) {for( register int j = i ; j ; j -= lowbit( j ) ) s ++;ones[ i ] = s; }

剩下就是常規(guī)的\(DSF\)

#include <bits/stdc++.h> #define lowbit( x ) ( x & -x ) using namespace std;const int N = 100 , n = 9; int maps[ 1 << n ] , ones[ 1 << n ] , row[n] , col[n] , cell[3][3]; char str[N];inline void init() //初始化 {for( register int i = 0 ; i < n ; i ++ ) row[i] = col[i] = ( 1 << n ) - 1 ;for( register int i = 0 ; i < 3 ; i ++ ){for( register int j = 0 ; j < 3 ; j ++ ) cell[ i ][ j ] = ( 1 << n ) - 1;} }inline int get( int x , int y ) //取交集 {return row[ x ] & col[ y ] & cell[ x / 3 ][ y / 3]; }inline bool dfs( int cnt ) {if( !cnt ) return 1; // 已經(jīng)填滿 register int minv = 10 , x , y;for( register int i = 0 ; i < n ; i ++ ){for( register int j = 0 ; j < n ; j ++ ){if( str[ i * 9 + j ] != '.' ) continue;register int t = ones[ get( i , j ) ];if( t < minv ) // 找到可能情況最少的格子 {minv = t;x = i , y = j ;}}}for( register int i = get( x , y ) ; i ; i -= lowbit( i ) ) // 枚舉這個格子填那些數(shù) {register int t = maps[ lowbit(i) ];row[x] -= 1 << t , col[y] -= 1 << t; // 打標(biāo)記 cell[ x / 3 ][ y / 3 ] -= 1 << t;str[ x * 9 + y ] = t + '1';if( dfs(cnt - 1 ) ) return 1;row[x] += 1 << t , col[y] += 1 << t; // 刪除標(biāo)記 cell[ x / 3 ][ y / 3 ] += 1 << t;str[ x * 9 + y ] = '.';}return 0; }int main() {for( register int i = 0 ; i < n ; i ++ ) maps[ 1 << i ] = i;for( register int i = 0 , s = 0 ; i < 1 << n ; i ++ , s = 0){for( register int j = i ; j ; j -= lowbit( j ) ) s ++;ones[ i ] = s; // i 這個數(shù)二進制中有多少個 1 }while( cin >> str , str[0] != 'e' ){init();register int cnt = 0;for( register int i = 0 , k = 0 ; i < n ; i ++ ){for( register int j = 0 ; j < n ; j ++ , k ++ ){if(str[k] == '.' ) { cnt ++ ; continue; } //記錄有多少個數(shù)字沒有填 register int t = str[k] - '1'; // 把已經(jīng)填入的數(shù)字刪除 row[ i ] -= 1 << t;col[ j ] -= 1 << t;cell[ i / 3 ][ j / 3 ] -= 1 << t;}}dfs( cnt );cout << str << endl;}return 0; }

0x23 剪枝

剪枝，就是減小搜索樹的規(guī)模、盡早的排除搜索樹中不必要的成分

優(yōu)化搜索順序
在一些問題中，搜索樹的各個層次、各個分支的順序是不固定的。不同的搜索順序會產(chǎn)生不同的搜索樹形態(tài)，其規(guī)模相差也很大。我們可以通過優(yōu)先搜索更有可能出現(xiàn)結(jié)果的分支來提前找到答案

排除等效冗余
在搜索的過程中，如果能夠判定搜索樹上當(dāng)前節(jié)點的幾個分支是等效的，這我們搜索其中一個分支即可

可行性剪枝
在搜索的過程中對當(dāng)前的狀態(tài)進行檢查，如果無論如何都不可能走到邊界我們就放棄搜索當(dāng)前子樹，直接回溯

最優(yōu)性剪枝
在搜索過程中假設(shè)我們已經(jīng)找到了某一個解，如果我們目前的狀態(tài)比已知解更劣就放棄繼續(xù)搜索下去因為無法比當(dāng)前解更優(yōu)呢么后面情況累加起來后一定比當(dāng)前解更劣，所以直接回溯

記憶化
可以記錄每個狀態(tài)的結(jié)果，在每次遍歷過程中檢查當(dāng)前狀態(tài)是否已經(jīng)被訪問過，若果被訪問過直接返回之前搜索的結(jié)果

AcWing 167.木棒

這是一道經(jīng)典的剪枝題

優(yōu)化搜索順序

把木棍從大到小排序，優(yōu)先嘗試比較長的木棍，越短的木棍適應(yīng)能力越強

排除等效冗余

限制加入木棍的順序必須是遞減的，因為假如有兩根木棍\(x,y(x<y)\)，先加入\(x\)和先加入\(y\)是等效的

如果上一根木棍失敗且和當(dāng)前木棍長度相同，這當(dāng)前木棍一定失敗

如過當(dāng)前木棍已經(jīng)拼成一個完整的木棍，當(dāng)后面拼接過程中失敗則當(dāng)前木棍無論怎么拼都一定會失敗，因為在重新嘗試的過程中會使用更多更小的木棍來拼成當(dāng)前木棍，但更小的木棍的適用性更強，卻失敗了，所以用更長的木棍嘗試也一定會失敗

#include <bits/stdc++.h> #pragma GCC optimize(3,"Ofast","inline") #pragma GCC optimize(2) using namespace std;const int N = 100; int n , m , a[N] , sum , cnt , len ; bool v[N];inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline bool cmp( int x , int y ) { return x > y; }inline bool dfs( int stick , int cur , int last) {if ( stick == cnt ) return 1;if ( cur == len ) return dfs( stick + 1 , 0 , 1 );register int fail = 0;for (register int i = last; i <= n; i++) // 剪枝 2 {if( v[i] || cur + a[i] > len || fail == a[i] ) continue;// fail == a[i] 剪枝 3 v[i] = 1;if ( dfs( stick , cur + a[i] , i + 1 ) ) return 1;v[i] = 0 , fail = a[i];if ( cur == 0 || cur + a[i] == len ) break;// cur + a[i] = len 剪枝 4 }return 0; }inline void work() { sum = n = 0;for( register int i = 1 ; i <= m ; i ++ ){register int x = read();if( x > 50 ) continue;a[ ++ n ] = x , sum += x;}sort( a + 1 , a + 1 + n , cmp );//剪枝 1 for( len = a[1] ; len <= sum ; len ++ ){if( sum % len ) continue;cnt = sum / len;memset( v , 0 , sizeof( v ) );if( dfs( 1 , 0 , 1 ) ) break;}printf( "%d\n" , len );return ; }int main() {while(1){m = read();if( m == 0 ) break;work();}return 0; }

0x24 迭代加深

深度優(yōu)先搜索（\(ID-DSF\)）就是每次選擇一個分支，然后不斷的一直搜索下去，直到搜索邊界在回溯，這種算法有一定的缺陷

比如下面這張圖，我要紅色點走到另一個紅色點

如果用普通的\(DFS\)前面的很多狀態(tài)都是無用的，因為子樹太深了

并且每到一個節(jié)點我都要儲存很多的東西\(BFS\)很不好存

這是就要用到迭代加深了

AcWing 170. 加成序列

這道題就是一個迭代加深搜索的模板題

為什么是迭代加深搜索呢？

分析題目給的性質(zhì)

如果使用\(DFS\)，你需要搜索很多層，并且第一個找到的解不一定最有解

如果使用\(BFS\)，你需要在隊列中儲存\(M\)個長度為\(n\)的數(shù)組(\(M\)是隊列長度)，不僅儲存非常麻煩并且還有可能會爆棧

所以通過迭代加深性質(zhì)就能很好的解決這個問題

限制序列的長度，不斷從已知的數(shù)中找兩個相加，到邊界時判斷一下，比較常規(guī)

優(yōu)化搜索順序

為了能夠盡早的達到\(n\),從大到小枚舉\(i\)，\(j\)

排除等效冗余

因為\(i\)，\(j\)和\(j\)，\(i\)是等效的所以保證\(j \le i\)

不同的\(i\),\(j\)可能出現(xiàn)\(a[i]+a[j]\)相同的情況，對相加結(jié)果進行判重

#include <bits/stdc++.h> using namespace std;const int N = 105; int n , m , a[N]; bitset< N > vis;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ) {x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline bool ID_dfs( int k ) {if( k > m ) return a[m] == n;vis.reset();for( register int i = k - 1 ; i > 0 ; i -- ){for( register int j = k - 1 ; j > 0 ; j -- ){register int cur = a[i] + a[j];if( cur > n || vis[ cur ] || cur < a[ k - 1 ]) continue;a[k] = cur;vis[ cur ] = 1;if( ID_dfs( k + 1 ) ) return 1;}}return 0; }inline void work() {for( m = 1 ; m <= n ; m ++ ){if( ID_dfs( 2 ) ) break;}for( register int i = 1 ; i <= m ; i ++ ) printf( "%d " , a[i] );puts("");return ; }int main() {a[1] = 1 , a[2] = 2;for( n = read() ; n ; n = read() ) work();return 0; }

雙向搜索

除了迭代加深外，雙向搜索也可以大大減少在深沉子樹上浪費時間

在一些問題中有明確的初始狀態(tài)和末狀態(tài)，呢么就可以采用雙向搜索

從初狀態(tài)和末狀態(tài)出發(fā)各搜索一半，產(chǎn)生兩顆深度減半的搜索樹，在中間交匯組合成最終答案

AcWing 171.送禮物

這到題顯然是一個\(DP\)，但是由于它數(shù)字的范圍非常大做\(DP\)肯定會\(T\)

所以這道題的正解就是\(DFS\)暴力枚舉所有可能在判斷

但是\(n\le 46\)所以搜索的復(fù)雜度是\(O(2^{46})\)依然會\(T\)

所以還是要想辦法優(yōu)化，這里用了到了雙向搜索的思想

我們將\(a[1\cdots n]\),分成\(a[1\cdots mid]\)和\(a[mid+1\cdots n]\)兩個序列

首先現(xiàn)在第一個序列中跑一次\(DFS\)求出所以可以產(chǎn)生的合法情況，去重，排序

然后在第二個序列中再跑一次\(DFS\)，求出的每一個解\(x\)就在第一序列產(chǎn)生的結(jié)構(gòu)中二分一個\(y\)滿足\(max(x),x\in\{ x | x + y \le W \}\)，更新答案

優(yōu)化

優(yōu)化搜索順序，從大到小搜索，很常規(guī)

我們發(fā)現(xiàn)第二次\(DFS\)中會多次二分，所以我們可以適當(dāng)?shù)臏p少第二個序列長度，來平衡復(fù)雜度。換句話來說就是適當(dāng)?shù)臏p少二分的次數(shù)，根據(jù)實測\(mid=\frac{n}{2}+2\)效果最好

#include <bits/stdc++.h> using namespace std;const int N = 50; int w , n ,tot , a[N] , mid , ans , m ; vector < int > s;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline void dfs_1( int x , long long sum ) {s.push_back( sum );if( x > mid ) return ;if( sum + a[x] <= w ) dfs_1( x + 1 , sum + a[x] );dfs_1( x + 1 , sum );return ; }inline void dfs_2( int x , long long sum ) {register auto t = lower_bound( s.begin() , s.end() , w - sum , greater<int>() );if( sum + *t <= w ) ans = max( ans , I(sum) + *t );if( x > n ) return ;if( sum + a[x] <= w ) dfs_2( x + 1 , sum + a[x] );dfs_2( x + 1 , sum );return ; }int main() {w = read() , m = read() ; for( register int i = 1 ; i <= m ; i ++ ){register int x = read();if( x > w ) continue;a[ ++ n ] = x;}mid = n >> 1 + 2;sort( a + 1 , a + 1 + n , greater<int>() );dfs_1( 1 , 0 );sort( s.begin() , s.end() );unique( s.begin() , s.end() );dfs_2( mid + 1 , 0);cout << ans << endl;return 0; }

0x25 廣度優(yōu)先搜索

\(BFS\) 全稱是 \(Breadth First Search\) ，中文名是寬度優(yōu)先搜索，也叫廣度優(yōu)先搜索。

是圖上最基礎(chǔ)、最重要的搜索算法之一。

所謂寬度優(yōu)先。就是每次都嘗試訪問同一層的節(jié)點。 如果同一層都訪問完了，再訪問下一層。

這樣做的結(jié)果是，\(BFS\) 算法找到的路徑是從起點開始的 最短 合法路徑。換言之，這條路所包含的邊數(shù)最小。

在 \(BFS\) 結(jié)束時，每個節(jié)點都是通過從起點到該點的最短路徑訪問的。

算法過程可以看做是圖上火苗傳播的過程：最開始只有起點著火了，在每一時刻，有火的節(jié)點都向它相鄰的所有節(jié)點傳播火苗。

AcWing 172. 立體推箱子

這到題是寬搜中比較有難度的一道

這道題中不變的是圖，變化的是物體的狀態(tài)，所以本題的難點就在于如何設(shè)計狀態(tài)

我們可以用一個三元組\((x,y,lie)\)來代表一個狀態(tài)（搜索樹上的一個節(jié)點）

當(dāng)\(lie=0\)時，物體立在\((x,y)\)上

當(dāng)\(lie=1\)時，物體橫向躺著，并且左半部分在\((x,y)\)上

當(dāng)\(lie=2\)時，物體縱向躺著，并且上半部分在\((x,y)\)上

并且用數(shù)組\(d[x][y][lie]\)表述從其實狀態(tài)到每個狀態(tài)所需要的最短步數(shù)

設(shè)計好狀態(tài)就可以開始搜索了

#include <bits/stdc++.h> using namespace std;const int N = 510; const int dx[4] = { 0 , 0 , 1 , -1 } , dy[4] = { 1 , -1 , 0 , 0 }; const int next_x[3][4] = { { 0 , 0 , -2 , 1 } , { 0 , 0 , -1 , 1 } , { 0 , 0 , -1 , 2 } }; const int next_y[3][4] = { { -2 , 1 , 0 , 0 } , { -1 , 2 , 0 , 0 } , { -1 , 1 , 0 , 0 } }; const int next_lie[3][4] = { { 1 , 1 , 2 , 2 } , { 0 , 0 , 1 , 1 } , { 2 , 2 , 0 , 0 } }; int n , m , d[N][N][3] , ans; char s[N][N]; struct rec{ int x , y , lie; } st , ed ; //狀態(tài) queue< rec > q;inline bool valid( int x , int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }bool operator == (rec a ,rec b ){ return a.x == b.y && a.y == b.y && a.lie == b.lie ;}inline void pares_st_ed() {for( register int i = 1 ; i <= n ; i ++ ){for( register int j = 1 ; j <= m ; j ++ ){if( s[i][j] == 'O') ed.x = i , ed.y = j , ed.lie = 0, s[i][j] = '.';else if( s[i][j] == 'X' ){for( int k = 0 ; k < 4 ; k ++ ){register int x = i + dx[k] , y = j + dy[k];if( valid( x , y ) && s[x][y] == 'X' ){st.x = min( i , x ) , st.y = min( j , y ) , st.lie = k < 2 ? 1 : 2;s[i][j] = s[x][y] = '.';break;}}}if( s[i][j] == 'X' ) st.x = i , st.y = j , st.lie = 0;} } }inline bool check( rec next ) {if( !valid( next.x , next.y ) ) return 0;if( s[next.x][next.y] == '#' ) return 0;if( next.lie == 0 && s[next.x][next.y] != '.' ) return 0;if( next.lie == 1 && s[next.x][next.y] == '#' ) return 0;if( next.lie == 2 && s[next.x][next.y] == '#' ) return 0;return 1; } int bfs() {for( register int i = 1 ; i <= n ; i ++ ){for( register int j = 1 ; j <= m ; j ++ ){for( register int k = 1 ; k <= n ; k ++ ) d[i][j][k] = -1;}}while( q.size() ) q.pop();d[st.x][st.y][st.lie] = 0 ; q.push( st );rec now , next;while( q.size() ){now = q.front() , q.pop();for( int i = 0 ; i < 4; i ++ ){next.x = now.x + next_x[now.lie][i] , next.y = now.y + next_y[now.lie][i] , next.lie = next_lie[now.lie][i];if (!check(next)) continue;if (d[next.x][next.y][next.lie] == -1) { d[next.x][next.y][next.lie] = d[now.x][now.y][now.lie]+1;q.push(next);if (next.x == ed.x && next.y == ed.y && next.lie == ed.lie) return d[next.x][next.y][next.lie]; // 到達目標(biāo)}}}return -1; }int main() {while( 1 ){cin >> n >> m;if( !n && !m ) break;for( register int i = 1 ; i <= n ; i ++ ) scanf( "%s" , s[i] + 1 );pares_st_ed();ans = bfs();if( ans == -1 ) puts("Impossible");else cout << ans << endl;}return 0; }

在上述的代碼中使用了\(next\_x,next\_y,next\_lie\)這三個數(shù)組來表示向四個方向移動的變化情況時寬搜中常用的一中技巧，避免了大量使用\(if\)語句容易造成混亂的情況

Luogu P3456 GRZ-Ridges and Valleys

這道題時一個寬搜的經(jīng)典題，如果用\(DFS\)會爆棧

看代碼就可以理解

#include<bits/stdc++.h> using namespace std;const int N = 1005; const int dx[8] = { -1 , -1 , -1 , 0 , 0 , 1 , 1 , 1 } , dy[8] = { -1 , 0 , 1 , -1 , 1 , -1 , 0 , 1 }; //向 8 個方向擴展 int n , maps[N][N] , valley , peak; bool vis[N][N] , v , p; struct node {int x , y; } _ , cur;// 儲存搜索狀態(tài) queue< node > q;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; } inline node make_node( int x , int y ) { _.x = x , _.y = y; return _; }inline int bfs() {register int ux , uy;while( !q.empty() ){cur = q.front() , q.pop();for( register int i = 0 ; i <= 7 ; i ++ ){ux = cur.x + dx[i] , uy = cur.y + dy[i];if( ux < 1 || ux > n || uy < 1 || uy > n ) continue;//判斷是否躍出邊界 if( maps[ux][uy] == maps[ cur.x ][ cur.y ] && !vis[ux][uy] ){//如果高度相同，打標(biāo)記繼續(xù)搜索vis[ux][uy] = 1;q.push( make_node( ux , uy ) );}else//判斷當(dāng)前聯(lián)通塊是 山峰 或 山谷{if( maps[ux][uy] > maps[cur.x][cur.y] ) p = 0;if( maps[ux][uy] < maps[cur.x][cur.y] ) v = 0;}}} } int main() {n = read() , v = 1;for( register int i = 1 ; i <= n ; i ++ ){for( register int j = 1 ; j <= n ; j ++ ){maps[i][j] = read();if( maps[i][j] != maps[1][1] ) v = 0; }}if( v ) puts("1 1") , exit(0);//特殊情況判斷for( register int i = 1 ; i <= n ; i ++ ){for( register int j = 1 ; j <= n ; j ++ ){if( vis[i][j] ) continue;//判斷當(dāng)前點是否是被搜索的聯(lián)通塊v = p = vis[i][j] = 1;q.push( make_node( i , j ) );bfs();peak += p , valley += v;}}cout << peak << ' ' << valley << endl;return 0; }

0x26廣搜變形

雙端隊列\(BFS\)

雙端隊列 \(BFS\) 又稱 \(0-1 BFS\)

適用范圍

在一張圖中，如果一張圖中，有些邊有邊權(quán)，有些邊沒有邊權(quán)，如果要搜索這個圖，就要用雙端隊列\(BFS\)

具體實現(xiàn)

在搜索過程中，如果遇到的沒有邊權(quán)的邊就加入隊頭，如果有邊權(quán)就加入隊尾

AcWing 175. 電路維修

可以把這張方格圖，抽象成點，然后把圖中有的邊當(dāng)成邊權(quán)為\(1\)，把沒有的邊當(dāng)作沒有邊權(quán)的邊

然后做雙端隊列\(BFS\)就好

#include <bits/stdc++.h> #define PII pair< int , int > using namespace std;const int N = 510 , INF = 0x7f7f7f7f; const int dx[4] = { -1 , -1 , 1 , 1 } , dy[4] = { -1 , 1 , 1 , -1 }; const int ix[4] = { -1 , -1 , 0 , 0 } , iy[4] = { -1 , 0 , 0 , -1 }; int n , m , T , t , d[N][N]; bool vis[N][N]; char g[N][N] , cs[] = "\\/\\/";inline int bfs() {deque< PII > q;memset( vis , 0 , sizeof( vis ) );memset( d , INF , sizeof( d ) );d[0][0] = 0;q.push_back( { 0 , 0 } );while( !q.empty() ){auto cur = q.front() ; q.pop_front();register int x = cur.first , y = cur.second;if( vis[x][y] ) continue;vis[x][y] = 1;for( register int i = 0 ; i < 4 ; i ++ ){register int a = x + dx[i] , b = y + dy[i];register int j = x + ix[i] , k = y + iy[i];if( a >= 0 && a <= n && b >= 0 && b <= m){ register int w = 0;if( g[j][k] != cs[i] ) w = 1;if( d[a][b] > d[x][y] + w ){d[a][b] = d[x][y] + w;if( w ) q.push_back( { a , b } );else q.push_front( { a , b } );}}}}if( d[n][m] == INF ) return -1;return d[n][m]; }inline void work() {cin >> n >> m;for( register int i = 0 ; i < n ; i ++ ) scanf( "%s" , g[i] );t = bfs();if( t == -1 ) puts("NO SOLUTION");else printf( "%d\n" , t );return ; }int main() {cin >> T;while( T -- ) work();return 0; }

優(yōu)先隊列\(BFS\)

這里就是利用優(yōu)先隊列的性質(zhì)，每次優(yōu)先擴展最優(yōu)的狀態(tài)

AcWing 176. 裝滿的油箱

這題要用到優(yōu)先隊列，因為普通的DFS會超時的

首先我們使用一個二元組\(\{city,fuel\}\)來表示一個狀態(tài)，每個狀態(tài)的權(quán)值就是到達這個狀態(tài)所需要的權(quán)值

然后們把所有的狀態(tài)都放入一個堆中，并且按照權(quán)值從小到大排序

每次我們?nèi)コ秧數(shù)脑剡M行擴展

如果當(dāng)前油箱還沒有滿，就擴展\(\{city,fuel+1\}\)這個狀態(tài)

遍歷以當(dāng)前邊為起點的所有邊，如果當(dāng)前油箱的油可以到達下一個城市，就擴展\(\{v , fuel -d[city][v\}\)這個狀態(tài)

所以當(dāng)我們第一次從對頭取出終點,就是最優(yōu)解

#include <bits/stdc++.h> #define F first #define S second using namespace std;const int N = 1005 , C = 105 , INF = 0x7f7f7f7f; int n , m , T , c , st , ed , tot , a[N] , head[N] , dist[N][C]; bool vis[N][C]; priority_queue< pair< int , pair< int , int > > > q; vector< pair< int , int > > e[N];inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline void work() {c = read() , st = read() , ed = read();while( !q.empty() ) q.pop();memset( vis , 0 , sizeof( vis ) );memset( dist , INF , sizeof( dist ) );dist[ st ][0] = 0;q.push( make_pair( 0 , make_pair( st , 0 ) ) );while( !q.empty() ){register int city = q.top().S.F , fuel = q.top().S.S;q.pop();if( city == ed ){cout << dist[city][fuel] << endl;return ;}if( vis[city][fuel] ) continue;vis[city][fuel] = 1;if( fuel < c && dist[city][fuel + 1 ] > dist[city][fuel] + a[city] ){dist[city][ fuel + 1 ] = dist[city][fuel] + a[city];q.push(make_pair( - dist[city][fuel] - a[city], make_pair( city , fuel + 1 ) ) );}for( auto it : e[city] ){register int y = it.F , z = it.S;if( z <= fuel && dist[y][ fuel - z ] > dist[city][fuel] ){dist[y][ fuel - z ] = dist[city][fuel];q.push(make_pair( - dist[city][fuel] , make_pair( y , fuel - z ) ) );}}}puts("impossible"); }int main() {n = read() , m = read();for( register int i = 0 ; i < n ; i ++ ) a[i] = read();for( register int i = 1 ; i <= m ; i ++ ){register int u = read() , v = read() , w = read();e[u].push_back( make_pair( v , w ) );e[v].push_back( make_pair( u , w ) );}T = read();while( T -- ) work();return 0; }

雙向\(BFS\)

雙向BFS的思想和0x24中雙向搜索是相同的，因為BFS是逐層搜索，所以會更好理解，同時算法實現(xiàn)也很簡單

從起始狀態(tài)，目標(biāo)狀態(tài)分別開始，兩邊輪流進行，每次各擴展一層。當(dāng)兩邊各自有一個狀態(tài)在記錄數(shù)組中發(fā)生重復(fù)時，就說明搜索過程中相遇，可以合并各自出發(fā)點到當(dāng)前的最少步數(shù)

//開始結(jié)點 和 目標(biāo)結(jié)點 入隊列 q //標(biāo)記開始結(jié)點為 1 //標(biāo)記目標(biāo)結(jié)點為 2 while( !q.empty() ) {//從 q.front() 擴展出新的s個結(jié)點//如果 新擴展出的結(jié)點已經(jīng)被其他數(shù)字標(biāo)記過//那么 表示搜索的兩端碰撞//那么 循環(huán)結(jié)束//如果 新的s個結(jié)點是從開始結(jié)點擴展來的//那么 將這個s個結(jié)點標(biāo)記為1 并且入隊q //如果 新的s個結(jié)點是從目標(biāo)結(jié)點擴展來的//那么 將這個s個結(jié)點標(biāo)記為2 并且入隊q }

0x27 A*

注：本小結(jié)在敘述過程中使用參照了\(cdcq\)和\(thu\)的\(ppt\),所以一些概念與我們常規(guī)的定義略有沖突

在之前的優(yōu)先隊列\(BFS\)中，我們通過記錄從起始狀態(tài)到當(dāng)前狀態(tài)的權(quán)值\(W\),并且按照\(W\)排序，這樣可以減少許多不必要的搜索

這其實就是一種貪心的思想，如果遇到當(dāng)前的權(quán)值比較小，但后面的權(quán)值非常大，此時在用這種套路就會增加很多不必要的搜索

所以也就有了啟發(fā)式搜索\(A\)，首先我們要定義一些符號方便理解

s//初始狀態(tài) t//目標(biāo)狀態(tài) n//當(dāng)前狀態(tài) g*[n] //從 s 到 n 的最小代價 h*[n] //從 n 到 t 的最小代價 f*[n] = h*[n] + g*[n]//從 s 到 t 的最小代價

對于每個狀態(tài),我們按照他的\(f[n]\)排序，每次取出最優(yōu)解，擴展?fàn)顟B(tài)，直到第一次擴展到\(t\)，結(jié)束循環(huán)

雖然\(A\)算法保證一定可以最先找到最優(yōu)解，但多數(shù)時候會因為求\(h^*[n]\)，會耗費很大的代價，導(dǎo)致時間復(fù)雜度變大

所以就有了另一種算法最佳圖搜索算法\(A^*\)，還是我們要定義一些符號

g[n] // g*[n] 的估計值 ，但是由于我們已經(jīng)訪問到當(dāng)前狀態(tài)所以g[n] == g*[n] h[n] // h*[n] 的估計值 f[n] = h[n] + g[n] // f*[n] 的估計值 稱為估價函數(shù)

只要保證\(h[n] \le h^*[n]\)，剩余不變\(A\)算法就變成了\(A^*\)算法

可以簡單的敘述下正確性，因為\(h[n] \le h^*[n]\)，即使估計函數(shù)不太準(zhǔn)確，導(dǎo)致路徑上的非最有狀態(tài)被提前擴展

但是由于\(g[n]\)不斷累加，\(f[n]\)會不段的逼近\(f^*[n]\)，所以最先擴展到狀態(tài)時一定還是最優(yōu)解，因為\(h[t]==0\)

另外如果\(h[n]=0\)的話，\(A^*\)算法就變成了優(yōu)先隊列\(BFS\),所以優(yōu)先隊列\(BFS\)就是估價函數(shù)不夠優(yōu)秀的\(A^*\)算法

所以如何設(shè)計一個優(yōu)秀的估價函數(shù)就是\(A^*\)算法的精髓

AcWing 178. 第K短路

聽說因為數(shù)據(jù)比較水，所以可以\(dijkstra\)第\(k\)次彈出也可以過

\(A^*\)的題都沒什么好說的，只要知道怎么設(shè)計估價函數(shù)其他就是模板了

我們看估價函數(shù)的定義式\(h[x]=f[x]+g[x]\)

我們發(fā)現(xiàn)\(g[x]\)是關(guān)鍵，\(g[x]\)的定義就是從當(dāng)前狀態(tài)的步數(shù)到目標(biāo)狀態(tài)的可能步數(shù)，且必須保證\(g[x]\le g^*[x]\)

不難想到求個最短路就好了，不過要求的是多源單匯最短路，且圖是個有向圖，用\(floyed\)也是不合適的

所以我們可以在反向圖上跑從T出發(fā)的單源多匯最短路的值作為\(g[x]\)即可

#include <bits/stdc++.h> #define PII pair< int , int > #define IPII pair< int , PII > #define F first #define S second using namespace std;const int N = 1005 , INF = 0x7f7f7f7f ; int n , m , vis[N] , g[N] , st , ed , k , ans; vector< PII > from[N] , to[N];inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; }inline void addedge( int u , int v , int w ) {to[u].push_back( { v , w } );from[v].push_back( { u ,w } ); }inline void dijkstra() {priority_queue< PII , vector < PII > , greater< PII > > q;memset( g , INF , sizeof( g ) );g[ed] = 0;q.push( { g[ed] , ed } );int u , v , dist , w ;while( !q.empty() ){u = q.top().S , dist = q.top().F , q.pop();if( vis[u] ) continue;for( auto it : from[u] ){v = it.F , w = it.S;if( g[v] <= g[u] + w ) continue;g[v] = g[u] + w;q.push( { g[v] , v } );}}return ; }inline void A_star() {priority_queue< IPII , vector< IPII > , greater< IPII > > q;memset( vis , 0 , sizeof( vis ) );q.push( { g[st] , { st , 0 } } );int u , v , w , dist;while( !q.empty() ){u = q.top().S.F , dist = q.top().S.S , q.pop();if( vis[u] >= k ) continue;vis[u] ++;if( u == ed && vis[u] == k ) printf( "%d\n" , dist ) , exit(0);for( auto it : to[u] ){v = it.F , w = it.S;if( vis[v] >= k ) continue;q.push( { dist + w + g[v] , { v , dist + w } } );}}return ; }int main() {n = read() , m = read();for( register int i = 1 ; i <= m ; i ++ ){register int u = read() , v = read() , w = read();addedge( u , v , w );}st = read() , ed = read() , k = read();if( st == ed ) k ++;dijkstra();A_star();puts( "-1" );return 0; }

0x28 IDA*

\(cdcq\):\(ID\)還是那個\(ID\),\(A^*\)還是那個\(A^*\)

首先我們設(shè)計一個估價函數(shù)，然后在\(ID-DFS\)的框架下進行搜索

如果當(dāng)前深度+未來估計深度 > 深度的限制 立即回溯

這就是\(IDA^*\)的核心，換言之\(IDA^*\)就是迭代加深的\(A^*\)

\(IDA^*\)算法的實現(xiàn)流程基本和\(ID - DFS\)相同

只需要咋搜索每次執(zhí)行前寫上這句即可

if( dep + f() > max_dep ) return ;

所以\(IDA^*\)和\(A^*\)共同精髓都是設(shè)計估價函數(shù)

并且要保證\(f(x)\le f^*(x)\) ,證明如下

紅色點是起始狀態(tài)，綠色點是當(dāng)前狀態(tài)，紫色為目標(biāo)，藍(lán)色線為我們迭代到的最大權(quán)值

我們現(xiàn)在要估計綠色到紫色點的權(quán)值，如果我么的估計值小于實際值，則已消耗的權(quán)值加估計值就一定小于最大權(quán)值這可以繼續(xù)搜索

如果不能保證估計權(quán)值小于實際權(quán)值，則可能會出現(xiàn)已消耗的權(quán)值加估計值大于最大權(quán)值，此時就不會繼續(xù)搜索綠色點的子樹，也就不可能的到達紫色點

所以不保證估計值小于實際值就不能保證正確性

AcWing 180. 排書

這道題就是經(jīng)典的\(IDA^*\)

由于n比較小，且最多搜索5層，所以可以直接用一個數(shù)組來存下每一層 的狀態(tài)

然后就是設(shè)計估價函數(shù)

我們可以每次修改一個區(qū)間

對于任意一種狀態(tài)下如果$p[i+1] \neq p[i]+1 \(則\)i$和i+1是一定要調(diào)開的，我們把這種情況稱作一個錯誤狀態(tài)

我們統(tǒng)計一下錯誤的狀態(tài)為\(cnt\)

我們的每一次操作最多可以改變3個錯誤狀態(tài)，所以最理想的狀態(tài)下就是$次可以把整個序列調(diào)整成目標(biāo)序列

所以就得到了一種估價函數(shù)\(f() = \left \lceil \frac{cnt}{3} \right \rceil\)

#include <bits/stdc++.h> using namespace std;const int N = 20; int T , n , q[N] , cur[5][N] , max_dep , ans; bool flag;inline int read() {register int x = 0;register char ch = getchar();while( ch < '0' || ch > '9' ) ch = getchar();while( ch >= '0' && ch <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ch - '0';ch = getchar();}return x; } inline int f() {register int cnt = 0;for( register int i = 1 ; i < n ; i ++ ){if( q[ i + 1 ] != q[i] + 1 ) cnt ++ ;}return (cnt + 2 ) / 3; } inline bool check() {for( register int i = 1 ; i <= n ; i ++ ) {if( q[i] == i ) continue;return 0;}return 1; } inline void ida_star( int dep ) {if( dep + f() > max_dep || flag ) return ;if( check() ){ans = dep , flag = 1;return ;}for( register int l = 1 ; l <= n ; l ++ ){for( register int r = l ; r <= n ; r ++ ){for( register int k = k + 1 ; k <= n ; k ++ ){memcpy( cur[ dep ] , q , sizeof( q ) );register int x , y;for( x = r + 1 , y = l ; x <= k ; x ++ , y ++ ) q[y] = cur[dep][x];for( x = l ; x <= r ; x ++ , y ++ ) q[y] = cur[dep][x];ida_star( dep + 1 );if( flag ) return ;memcpy( q , cur[dep] , sizeof( q ) );}}}return ; }inline void work() {n = read() , flag = 0;for( register int i = 1 ; i <= n ; i ++ ) q[i] = read();for( max_dep = 1 ; max_dep <= 4 , !flag ; max_dep ++ ) ida_star(0);if( flag ) printf( "%d\n" , ans );else puts("5 or more");return ; }int main() {T = read();while( T -- ) work();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mark-X/p/11519097.html

總結(jié)

以上是生活随笔為你收集整理的0x20 搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。