1. 今天講旅行商問題ms大家都沒聽懂... 因?yàn)?a title="2010 HangZhou Regional Problem B">這題已經(jīng)捉出來了，所以就來個(gè)口味比較重的這道題吧

   2. 數(shù)據(jù)好弱... 如果是個(gè)團(tuán)的話，我的程序要跑5s....

   3. 好困... 代碼和題解都寫挫了，見諒啊，今天講一天課了...

    關(guān)于以大家喜聞樂見的TSP問題為首的一類基于子集和路徑的動(dòng)態(tài)規(guī)劃的一些介紹在這里...

    如果不喜歡看那么多我就簡單的講講吧...

    首先說下如何在一個(gè)圖上求哈密頓路的個(gè)數(shù)：

        dp[mask][u]表示以u(píng)為終點(diǎn)，遍歷過mask集合的點(diǎn)的哈密頓路的個(gè)數(shù)

        轉(zhuǎn)移就是dp[mask][u] = sum(dp[mask ^ (1<<u)][v]) 其中存在一條路 v->u

        dp[1 << u][u] = 1

    記憶化搜索很好寫

    

    好了，下面講如何解這道題：

    比較苦b的是 0 -> 1 ->2 和 2 -> 0 ->1 算做一種... 所以枚舉所有從u到v的哈密頓路是不行的...

    那么我們不妨設(shè)： 對(duì)于一個(gè)環(huán) a0 -> a1 -> ... -> a0 都以標(biāo)號(hào)最小的點(diǎn)為起點(diǎn)...

    這樣狀態(tài)dp[mask][i] 可以表示成以集合mask中標(biāo)號(hào)最小的點(diǎn)為起點(diǎn)，以i為終點(diǎn)的哈密路的個(gè)數(shù)

    如果終點(diǎn)可以到達(dá)起點(diǎn)，就把這個(gè)加到答案當(dāng)中去...

 

    還有個(gè)問題是這個(gè)是無向圖， 1 -> 2 ->3 和3 ->2 ->1 是一樣的... 所以答案要除以2...

    

 1 #include<iostream> 
2 #include<cstring>
 3 #include<bitset>
 4 #include<cstdio>
 5 using namespace std;
 6 #define re(i,n) for(int i=0;i<(n);i++)
 7 #define re3(i,n) for(int i=1;i<(n);i++)
 8 #define clr(a,n) memset(a,n,sizeof(a))
 9 #define debug1
10 typedef long long ll;
11 ll dp[1 << 19][20];
12 ll lowbit[1 << 19],sum;
13 bool G[20][20];
14 inline bool _1(int mask,int v) {return mask & (1 << v);}
15 int n,m;
16 ll dfs(int mask, int u){
17     ll &ans = dp[mask][u];
18     #ifdef debug
19         bitset<5> MASK(mask);
20     #endif
21     int tmp = mask, cnt = 0;
22     while(tmp) cnt += tmp&1, tmp >>=1;
23     if(ans >= 0) return ans;
24     ans = 0;
25     int v;
26     for(v = lowbit[mask] ; v<n; v++)
27         if(v!=u && _1(mask,v) && G[u][v] &&(v!=lowbit[mask] || cnt == 2)) 
28             ans += dfs(mask ^ (1 << u), v);
29     v = lowbit[mask];
30     #ifdef debug
31 //        bitset<5> MASK(mask);
32 //        cout<<MASK.to_string()<<" "<<u<<" "<<v<<" "<<ans<<endl;
33     #endif
34     if(G[u][v] && cnt >2) {
35         sum += ans;
36         #ifdef debug
37         cout<<MASK.to_string()<<" "<<u<<" "<<ans<<endl;
38         #endif
39     }
40     return ans;
41 }
42 int main(){
43     re3(i,1<<19){
44         int msk = i,t=0;
45         while(msk&1^1) t++, msk >>= 1;
46         lowbit[i] = t;
47     }
48     while( cin >> n >> m){
49         int u,v;
50         clr(dp,-1); clr(G,0);
51         re(i,m) {
52             scanf("%d%d",&u,&v);
53             u--; v--;
54             G[u][v] = G[v][u] = 1;
55         }
56         #ifdef debug
57         n = 19;
58         re(i,n) re(j,n) if(i!=j)G[i][j] = 1;
59         #endif
60         int n_mask = 1 << n;
61         re(i,n) dp[1<<i][i] = 1;
62         sum  = 0;
63         re(mask,n_mask) {
64             v = lowbit[mask];
65             re(i,n) if(_1(mask,i) && G[v][i])
66                 dfs(mask,i);
67         }    
68         cout << sum/2 <<endl;
69     }
70 }
71