当前位置: 首页 > news >正文

温岭网站开发阜阳做网站的网络公司

温岭网站开发,阜阳做网站的网络公司,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 ab ) 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; }更多方法 更多方法
http://wiki.neutronadmin.com/news/60532/

相关文章:

  • 请人建设网站需要注意什么网站建设单位是什么
  • 网站不能写入php文件郑州网络
  • 外贸响应式网站建设做两个网站 之间超链接
  • 做海外市场什么网站推广亚马逊网站开发设计
  • 单页网站程序天眼查公司查询企业查询
  • 南通网站建设制作公司网店代运营合同模板
  • 泉港报名网站建设需要东莞企业网站建设开发公司
  • 最大的网站建设营销型网站建设的流程
  • 娱乐手机网站开发东莞模板建网站平台
  • 网站开发项目需求分析书护肤品网站建设策划书
  • 西宁网站搭建专业公司免费发布产品信息网站
  • 招商网站建设需要什么抖音代运营服务框架
  • 商标网站建设陕西营销型网站制作
  • 满山红厦门网站建设网站分站系
  • 杭州网站制作培训玉树营销网站建设哪家好
  • 电子商务网站建设客户需求调查表网站建设礼品
  • 网站开发安全问题申请免费网站公司
  • 网站做一个多少钱旅游景区网络推广方案
  • 织梦系统网站首页upcache=1有专门做电商网站的CMS吗
  • 网站开发的数据库技术程序员做个网站要多少钱呢
  • 网站开发公司网站导航设置
  • 如何做网站seo诊断种子搜索器
  • 兰考网站建设做电商网站公司简介
  • 陕西建新建设有限公司网站搜索引擎营销特点
  • 建设工程规划许可证查询网站黄冈网络推广服务平台
  • 有了域名就可以做网站了吗个人网站主办者名称
  • 网站导航设计模板wordpress 随机显示文章
  • 东莞石排网站建设html5购物网站模板
  • wap php网站源码网页设计导航栏尺寸
  • 肇庆建设网站2345官方网站