温岭网站开发,阜阳做网站的网络公司,wordpress 调用单页,万网网站安装CF11D 题目解题思路A Simple Task题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 分析Code更多方法 题目
原题链接
解题思路
A Simple Task
题面翻译
求无向图中的简单环个数#xff0c;保证不存在重边和自环。
简单环#xff1a;除起点外#… CF11D 题目解题思路A Simple Task题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 分析Code更多方法 题目
原题链接
解题思路
A Simple Task
题面翻译
求无向图中的简单环个数保证不存在重边和自环。
简单环除起点外其余的点都只出现一次的回路。
题目描述
Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no repeated vertices or edges.
输入格式
The first line of input contains two integers n n n and m m m ( 1 ≤ n ≤ 19 1\le n\le19 1≤n≤19 , 0 ≤ m 0\le m 0≤m ) – respectively the number of vertices and edges of the graph. Each of the subsequent $ m $ lines contains two integers a a a and b b b , ( 1 ≤ a , b ≤ n 1\le a,b\le n 1≤a,b≤n , a ≠ b a≠b ab ) indicating that vertices a a a and b b b are connected by an undirected edge. There is no more than one edge connecting any pair of vertices.
输出格式
Output the number of cycles in the given graph.
样例 #1
样例输入 #1
4 6
1 2
1 3
1 4
2 3
2 4
3 4样例输出 #1
7提示
The example graph is a clique and contains four cycles of length 3 and three cycles of length 4.
分析
考虑用状压DP 令 f [ j ] [ i ] f[j][i] f[j][i] 表示 n n n 个节点走过的状态起点为 i i i 中最小的 1 1 1 的位置且终点为 j j j 的路径总数。
考虑转移方程 f [ j ] [ i ] f[j][i] f[j][i] 转移至 f [ k ] [ i ∣ ( 1 ( k − 1 ) ) ] f[k][i|(1(k-1))] f[k][i∣(1(k−1))]由题可得是直接累加的但必须满足以下条件
状态 f [ j ] [ i ] f[j][i] f[j][i] 存在。 j j j 能到达 k k k。 k k k 大于 i i i 中最小的 1 1 1 的位置。 i i i 中没有 k k k 这个位置。
那么如果已经有了 k k k 这个点且 k k k 就为起点那就是找到环了直接统计即可。
注意
初始化 f[i][1(i-1)]1;即出发的点。
转移 同上 if(i(1(k-1))){if(lowbit(i)(1(k-1)))ansf[j][i];}elsef[k][i|(1(k-1))]f[j][i];统计答案 会有两个不合法情况 1 1 1 是每一条单独的边会被算为答案 2 2 2 是合法的环其反环会被多算一遍。 所以最终答案为 a n s − m 2 {\Large \frac{ans-m}{2}} 2ans−m。
Code
#includebits/stdc.h
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;
const int N119;
int f[20][N],n,m,x,y,a[101][101],ans;
inline int lowbit(int x)
{return x-x;
}
signed main()
{IOS;cinnm;for(int i1;im;i)cinxy,a[x][y]a[y][x]1;for(int i1;in;i)f[i][1(i-1)]1;for(int i0;i(1n);i){for(int j1;jn;j){if(!f[j][i])continue;for(int k1;kn;k){if(!a[j][k])continue;if(lowbit(i)(1(k-1)))continue;if(i(1(k-1))){if(lowbit(i)(1(k-1)))ansf[j][i];}elsef[k][i|(1(k-1))]f[j][i];}}}cout(ans-m)/2;return 0;
}更多方法
更多方法
