http://codeforces.com/problemset/problem/11/D
题意很明确了 找多少个简单环
首先考虑环怎么找
简单的会想到 用状态压缩dp的方法
F[S][I]已经走过了S集合,且结束在I点的方案树
当出现一个环时,头尾一定相连,此时结束点以及可以表示出来了
考虑如何判断首尾相连,以及对于一个环来说,可能存在重复,这两个问题怎么解决
前面这个有点恶心,看一下后面这个怎么解决
这个重复问题,一般是固定一个点,然后再搞
那么问题来了固定那个点为起始点呢??
不失一般性的,我们以集合中lowbit位置的点作为起点
那么很显然,起点和终点都有了
可以愉快的进行dp了
又因为是无向图
显然有一条边别搞做一个环的情况,和环转的顺序不同的情况
于是答案要做相应处理....
到这里再仔细想想怎么写,过一过
经验:嘛,做题最好把已知问题罗列出来,然后(会发现可以帮助思考....(当然抄题解也是不错选择))
还有就是要考虑答案的不完全性
#include<bits/stdc++.h> using namespace std; long long n,m,ans=0; long long tu[25][25]; long long f[1<<20][20]; int main(){ memset(tu,0x7f,sizeof(tu)); memset(f,0,sizeof(f)); cin>>n>>m; for(int i=1;i<=m;i++){ long long x,y; cin>>x>>y,tu[x-1][y-1]=tu[y-1][x-1]=1; } for(int i=0;i<n;i++)f[1<<i][i]=1; for(int S=0;S<(1<<n);S++){ for(int i=0;i<n;i++){ if(!f[S][i])continue; for(int j=0;j<n;j++){ if(((1<<j)<(S&(-S)))||tu[i][j]!=1)continue; if((1<<j)&S){ if((1<<j)==(S&(-S)))ans+=f[S][i]; } else{ f[S|(1<<j)][j]+=f[S][i]; } } } } cout<<(ans-m)/2<<endl; }
原文：https://www.cnblogs.com/shatianming/p/12266887.html
