首页 > 代码库 > 状压dp找寻环的个数 Codeforces Beta Round #11 D
状压dp找寻环的个数 Codeforces Beta Round #11 D
http://codeforces.com/problemset/problem/11/D
题目大意:给你n个点,m条边,找该图中有几个换
思路:定义dp[i][j]表示i是圈的集合,j表示该集合的终点,定义起点为这些走过的点里面最小的
//看看会不会爆int!数组会不会少了一维! //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha\n") const int maxn = 19; LL dp[1 << maxn][maxn + 5]; int a[maxn + 5][maxn + 5]; int n, m; void get_min(int val, int &cnt, int &st){ int pos = 0; while (val){ if (val & 1) st = min(st, pos), cnt++; val >>= 1; pos++; } } ///定义dp[i][j]表示i是圈的集合,j表示该集合的终点,定义起点为这些走过的点里面最小的 int main(){ cin >> n >> m; for (int i = 1; i <= m; i++){ int u, v; scanf("%d%d", &u, &v); u--, v--; a[u][v] = a[v][u] = 1; } LL ans = 0; for (int i = 0; i < n; i++) dp[1 << i][i] = 1;///初始化 for (int i = 1; i < (1 << n); i++){ int cnt = 0, st = n; get_min(i, cnt, st); for (int j = 0; j < n; j++){ if (dp[i][j]){///目前集合为i,终点为j。而且根据放入集合的顺序,j必然是在i集合里面的 if (a[st][j] && cnt >= 3){///放入集合的最终的终点一定得是在st的旁边。否则会将形不成环的放入ans中 ans += dp[i][j]; } for (int k = st + 1; k < n; k++){///放入终点大于st的。根据定义st必然为最小的起点。 ///然后k<st的已经在更小的状态中全部都计算过了 if (a[j][k] && !(i & (1 << k))){ dp[i | (1 << k)][k] += dp[i][j]; } } } } } /*haha; for(int i = 0; i < n; i++){ for (int j = 0; j < (1 << n); j++){ printf("%lld ", dp[j][i]); } cout << endl; }*/ cout << ans / 2 << endl; return 0; }
状压dp找寻环的个数 Codeforces Beta Round #11 D
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。