状压dp好题.....算把..

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;
}