這道題目如果數(shù)據(jù)很小的話。我們通過這個(gè)dfs就可以完成深搜：

void dfs(int s) {if (s==N){minLen=min(minLen,totalLen);return ;}for (int i=0;i<G[s].size();i++){Road r=G[s][i];if (r.t+totalCost>K)continue;if (!visited[r.d]){visited[r.d]=1;totalLen+=r.L;totalCost+=r.t;dfs(r.d);totalCost-=r.t;totalLen-=r.L;visited[r.d]=0;}} }

我們可以看一下這個(gè)代碼，意思就是說，如果找邊的時(shí)候，我們已經(jīng)搜索到了終點(diǎn)，也就是s==N的時(shí)候，我們就直接改寫minLen，然后返回到上一層，進(jìn)行totalCost，totalLen和visited數(shù)組的返回工作，因?yàn)槲覀冞@次走的是這一條路，當(dāng)我們返回的時(shí)候，就將這條路的終點(diǎn)標(biāo)記全部還原，因?yàn)閺倪@條路的起始點(diǎn)還可能會(huì)有其它的路，如果不把它還原的話，其它的路就被封死了，深搜就無法進(jìn)行的很完全了，不能說是遍歷了。

我們對(duì)于以s為起點(diǎn)的邊進(jìn)行遍歷，發(fā)現(xiàn)邊r的花費(fèi)加上之前的總花銷已經(jīng)超過K，總錢數(shù)了，我們就跳過這一條邊，這是第一次剪枝。

如果我們沒有訪問過邊r的終點(diǎn)d時(shí)，我們就把它訪問位設(shè)置為1，總路程加上r邊長(zhǎng)，總花費(fèi)加上r邊的過路費(fèi)，然后深搜d。

這是可以通過一些較小的數(shù)據(jù)的，但是這道題中的數(shù)據(jù)很大，而dfs中又做了很多的無用功，所以我們進(jìn)行以下的剪枝：

如果d點(diǎn)沒有被訪問過，我們就判斷如果這次走到點(diǎn)d的時(shí)候，總路程已經(jīng)超過minLen了，也就是之前找到的最短路，我們就跳過這個(gè)終點(diǎn)的深搜，我們直接不走這條路了。

這個(gè)剪枝還是不夠，所以我們拿空間換取時(shí)間，我們?cè)O(shè)置一個(gè)minL[110][10010]數(shù)組，minL[k][m]表示之前走到點(diǎn)k并且花費(fèi)為m的最短長(zhǎng)度。

如果我們這次走到點(diǎn)k，并且花銷為m，但是我們的路程已經(jīng)大于這個(gè)最短長(zhǎng)度了，我們就跳出這重循環(huán)，執(zhí)行循環(huán)的下一次。

因?yàn)樗囊馑?#xff0c;也就是說，我們每走過一個(gè)點(diǎn)，我們就進(jìn)行一次比較，確保我們不花相同的錢，走更遠(yuǎn)的路，這個(gè)剪枝極為有效，直接可以過。

代碼如下：

#include <iostream> #include <vector> #include <cstring> using namespace std; int N,K,R; struct Road {int d,L,t; }; vector < vector<Road> > G(110);int minLen; int minL[110][10010]; int totalLen; int totalCost; int visited[110];void dfs(int s) {if (s==N){minLen=min(minLen,totalLen);return ;}for (int i=0;i<G[s].size();i++){Road r=G[s][i];if (r.t+totalCost>K)continue;if (!visited[r.d]){if (totalLen+r.L>=minLen)continue;if (totalLen+r.L>=minL[r.d][r.t+totalCost])continue;visited[r.d]=1;totalLen+=r.L;minL[r.d][r.t+totalCost]=totalLen;totalCost+=r.t;dfs(r.d);totalCost-=r.t;totalLen-=r.L;visited[r.d]=0;}} }int main() {cin>>K>>N>>R;for (int i=0;i<R;i++) {int s;Road r;cin>>s>>r.d>>r.L>>r.t;if (s!=r.d) {G[s].push_back(r);}}memset(visited,0,sizeof(visited));for (int i=0;i<110;i++) {for (int j=0;j<10010;j++) {minL[i][j]=1<<30;}}totalLen=0;totalCost=0;minLen=1<<30;visited[1]=1;dfs(1);if (minLen<(1<<30))cout<<minLen<<endl;else cout<<-1<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xyqxyq/p/10211350.html

總結(jié)

以上是生活随笔為你收集整理的POJ-1724 深搜剪枝的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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