Description

A國(guó)有n個(gè)城市，編號(hào)為1到n，任意兩個(gè)城市之間有一條路。shlw閑得沒事干想周游A國(guó)，及從城市1出發(fā)，經(jīng)過(guò)且僅經(jīng)過(guò)除城市1外的每個(gè)城市1次（城市1兩次），最后回到城市1。由于shlw很傻，他只愿意走一定長(zhǎng)度，多了少了都不干，現(xiàn)在他想知道一共有多少種方案可供選擇。

Input

第一行為兩個(gè)整數(shù)n，l，分別為城市數(shù)和路程總長(zhǎng)。
之后n行，每行n個(gè)整數(shù)，其中第i行第j列為Ai,j，滿足Ai,i=0;Ai,j=Aj,i。

Output

輸出共1行，為總方案數(shù)。

Sample Input

3?6
0?1?3
1?0?2?
3?2?0

Sample Output

2

Data Constraint

對(duì)于30%，1<=n<=10
對(duì)于另外30%，1<=n<=14,1<=l<=30
對(duì)于100%，1<=n<=14,1<=Ai,j<=100,000,000,1<=l<=2,000,000,000
悄悄告訴你：數(shù)據(jù)的答案都很大，反正直接輸0是沒分的，但都在int范圍內(nèi)。
為了降低題目難度，Ai，j的種類數(shù)不會(huì)太多

?

題解

• 題目大意：有n個(gè)城市，問(wèn)每個(gè)城市都走一遍，路徑長(zhǎng)度剛好為L(zhǎng)的方案數(shù)
• 30%，暴力亂搜就好了，O(n!)
• 60%，n<=14，狀壓dp，設(shè)f[i][j][k]表示當(dāng)前經(jīng)過(guò)的點(diǎn)的狀態(tài)為i，現(xiàn)在在點(diǎn)j，當(dāng)前路徑長(zhǎng)為k，O(2^n*n^2*30)，聽說(shuō)加個(gè)map可以跑70分
• 100%，n<=14，折半搜索可以過(guò)
• 記前半段除了1與i長(zhǎng)度為n1，后半段為n2，那么如果確定了i，只要滿足前半段與后半段經(jīng)過(guò)的點(diǎn)不重復(fù)且路徑總長(zhǎng)為l就可以計(jì)算答案了
  
• 具體來(lái)說(shuō)就是就是枚舉一個(gè)點(diǎn)i，枚舉前半段的所有情況，用hash記下來(lái),再枚舉后半段的所有情況
• 并在hash中找到與之對(duì)應(yīng)的前半段，統(tǒng)計(jì)進(jìn)答案中就好了

代碼

?

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #define mo 19260817 5 #define ll long long 6 #define N 15 7 using namespace std; 8 int n,m,l,a[N][N],f[mo],ans,i; 9 ll g[mo]; 10 ll calc(int x,int y,int k){ return x*32768000000000ll+y*2000000000ll+k; } 11 int gethash(int x,int y,int k) 12 { 13 ll r=calc(x,y,k); 14 for (i=r%mo;g[i]&&g[i]!=r;++i==mo?i=0:i); 15 return i; 16 } 17 void dfs1(int d,int x,int y,int k) 18 { 19 if (x&&k>=l) return; 20 if (d>=m) 21 { 22 int p=gethash(x,y,k); 23 g[p]=calc(x,y,k),f[p]++; return; 24 } 25 for (int i=1;i<n;i++) if (!(y>>i&1)) dfs1(d+1,i,y|1<<i,k+a[x][i]); 26 } 27 void dfs2(int d,int x,int y,int k) 28 { 29 if (x&&k>=l) return; 30 if (d>=m) 31 { 32 int p=gethash(x,((~y)&((1<<n)-1))|1|1<<x,l-k); 33 ans+=f[p]; return; 34 } 35 for (int i=1;i<n;i++) if (!(y>>i&1)) dfs2(d+1,i,y|1<<i,k+a[x][i]); 36 } 37 int main() 38 { 39 scanf("%d%d",&n,&l); 40 for (int i=0;i<n;i++) for (int j=0;j<n;j++) scanf("%d",&a[i][j]); 41 m=n/2,dfs1(0,0,1,0),m=n-m,dfs2(0,0,1,0),printf("%d",ans); 42 }

?

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

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[折半搜索][has] Jzoj P4250 路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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