状态压缩的动态规划

以洛谷无向图求环问题为例

#include<bits/stdc++.h>
using namespace std;#define ll long long 
#define reg register int
int n,m;int a[19][19];ll f[1<<19][19];ll res=0;
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int j,k;cin>>j>>k;a[j-1][k-1]=a[k-1][j-1]=1;}for(int i=0;i<n;i++)f[1<<i][i]=1;for(reg i=1;i<(1<<n);i++){for(reg j=0;j<n;j++){if(!f[i][j])continue;for(reg k=0;k<n;k++){if(a[j][k]==0)continue;if((i&-i)>(1<<k))continue;if((1<<k)&i){if((1<<k)==(i&-i))res+=f[i][j];}elsef[i|1<<k][k]+=f[i][j];}}}cout<<(res-m)/2;
}