算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

   请问在点数为V(V<20)的无向图中,长度不小于3的简单回路有多少个?(保证结果可以用long long表示, 且图中无自环或者重边)

吐槽:

   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 
posted on 2012-04-29 22:14 西月弦 阅读(765) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理