织梦网站做中英文双语言版本,接工程的app软件,也是网络品牌建设和推广的基础,网站落地页如何做正题
题目链接:https://www.luogu.com.cn/problem/CF11D 题目大意
给出nnn个点mmm条边的一张简单无向图#xff0c;求它的简单环的个数。 1≤n≤191\leq n\leq 191≤n≤19 解题思路
首先算重的问题很麻烦但也是解决这题的关键。
因为防止算重那么我们就只考虑在每个环编号…正题
题目链接:https://www.luogu.com.cn/problem/CF11D 题目大意
给出nnn个点mmm条边的一张简单无向图求它的简单环的个数。
1≤n≤191\leq n\leq 191≤n≤19 解题思路
首先算重的问题很麻烦但也是解决这题的关键。
因为防止算重那么我们就只考虑在每个环编号最小的节点统计一次。
枚举一个起点然后后面就只走编号大于其的节点用状压计算方案数即可。
时间复杂度O(2nn2)O(2^nn^2)O(2nn2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N19;
ll n,m,f[N][1N],ans;
bool a[N][N];
signed main()
{scanf(%lld%lld,n,m);for(ll i1,x,y;im;i){scanf(%lld%lld,x,y);x--;y--;a[x][y]a[y][x]1;}ll MS(1n),pre0;for(ll p0;pn;p){pre|(1p);for(ll s0;sMS;s){if(spre)continue;for(ll i0;in;i)f[i][s]0;}f[p][0]1;for(ll s0;sMS;s){if(spre)continue;for(ll ip;in;i){if(!f[i][s])continue;for(ll jp1;jn;j){if((sj)1)continue;if(a[i][j])f[j][s|(1j)]f[i][s];}if(a[i][p]s!(s-s))ansf[i][s];}}}printf(%lld\n,ans/2);return 0;
}
