Codeforces 11D A Simple Task 统计简单无向图中环的个数（非原创）

太难了，学不会。看了两天都会背了，但是感觉题目稍微变下就不会了。dp还是摸不到路子。

附ac代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 typedef long long ll;
 8 ll dp[1<<20][20],ans=0;
 9 vector<int>e[20];
10 int lowbit(int x)
11 {
12     return x&(-x);
13 }
14 int main()
15 {
16     ios::sync_with_stdio(false);
17     int n,m,f,t;
18     cin>>n>>m;
19     for(int i=0;i<m;++i)
20     {
21         cin>>f>>t;
22         e[f-1].push_back(t-1);
23         e[t-1].push_back(f-1);
24     }
25     for(int i=0;i<n;++i)
26     dp[1<<i][i]=1;
27     for(int sta=1;sta<(1<<n);sta++)
28     {
29         for(int i=0;i<n;++i)
30         {
31             if(dp[sta][i])
32             {
33                 for(int k=0;k<e[i].size();++k)
34                 {
35                     int j=e[i][k];
36                     if(lowbit(sta)>(1<<j))  //如果该点比第一个点还要小，就跳过
37                     continue;
38                     if(sta&(1<<j))
39                     {
40                         if(lowbit(sta)==(1<<j))//如果i和该状态的起点（即最低位）联通，则记录
41                         ans+=dp[sta][i];
42                     }
43                     else
44                     {
45                         dp[sta|(1<<j)][j]+=dp[sta][i];//否则转移状态
46                     }
47                 }
48             }
49         }
50     }
51     ans=(ans-m)/2;
52     cout<<ans<<endl;
53     return 0;
54 }

View Code

附学习博客：http://blog.csdn.net/fangzhenpeng/article/details/49078233