1. 今天讲旅行商问题ms大家都没听懂... 因为这题已经捉出来了，所以就来个口味比较重的这道题吧

   2. 数据好弱... 如果是个团的话，我的程序要跑5s....

   3. 好困... 代码和题解都写挫了，见谅啊，今天讲一天课了...

    关于以大家喜闻乐见的TSP问题为首的一类基于子集和路径的动态规划的一些介绍在这里...

    如果不喜欢看那么多我就简单的讲讲吧...

    首先说下如何在一个图上求哈密顿路的个数：

        dp[mask][u]表示以u为终点，遍历过mask集合的点的哈密顿路的个数

        转移就是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的哈密顿路是不行的...

    那么我们不妨设： 对于一个环 a0 -> a1 -> ... -> a0 都以标号最小的点为起点...

    这样状态dp[mask][i] 可以表示成以集合mask中标号最小的点为起点，以i为终点的哈密路的个数

    如果终点可以到达起点，就把这个加到答案当中去...

 

    还有个问题是这个是无向图， 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