neuq-acm预备队训练week 9 P8604 [蓝桥杯 2013 国 C] 危险系数
题目背景
抗日战争时期,冀中平原的地道战曾发挥重要作用。
题目限制

题目描述
地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。
我们来定义一个危险系数 DF(x,y):
对于两个站点 x 和 y(x!=y), 如果能找到一个站点 z,当 z 被敌人破坏后,x 和 y 不连通,那么我们称 z 为关于 x,y 的关键点。相应的,对于任意一对站点 x 和 y,危险系数 DF(x,y) 就表示为这两点之间的关键点个数。
本题的任务是:已知网络结构,求两站点之间的危险系数。
输入格式

解题思路
这题可以用dfs来解,具体看代码
AC代码
#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,ans,cnt[1010],sum;
bool b[1010],a[1010][1010];
void dfs(int N);
int main()
{scanf("%d%d",&n,&m);while(m--){scanf("%d%d",&u,&v);a[u][v]=a[v][u]=1;//无向,令u到v和v到u为1}scanf("%d%d",&u,&v);dfs(u);if(sum>0){for(int i=1;i<=n;i++)if(cnt[i]==sum) //如果这个点被走过的总次数与路径总数相等(必经点)ans++; //那么删去这个点起点与终点间一定不连通。printf("%d",ans-1); //因为终点也被算在内,所以总危险系数要减去起点的1。}elseprintf("-1"); //如果无路径连通则输出-1return 0;
}
void dfs(int N)
{if(N==v) //如果到终点{sum++; //路径总数加一for(int i=1;i<=n;i++)if(b[i]==1)cnt[i]++;//每个被走过的点,被走总次数加一}else{for(int i=1;i<=n;i++)if(a[N][i]==1&&b[i]==0)//如果未被走过{b[i]=1;//标记dfs(i);b[i]=0;//回溯}}
}
相关文章:
neuq-acm预备队训练week 9 P8604 [蓝桥杯 2013 国 C] 危险系数
题目背景 抗日战争时期,冀中平原的地道战曾发挥重要作用。 题目限制 题目描述 地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。 我们来定义一个危险系数 DF…...
【BIG_FG_CSDN】*VMware17pro*Linux*Redhit6网络管理(个人向——学习笔记)
物理机中的网络 查看物理网络的方法 “网络连接”—>单点选中网络的选项-->菜单栏中“查看此连接状态”-->“详细信息” “网络连接”中的VM网卡 在主机上对应的有VMware Network Adapter VMnet1和VMware Network Adapter VMnet8两块虚拟网卡,它们分别…...
Nginx location+Nginx rewrite(重写)(新版)
Nginx locationNginx rewrite(重写) Nginx locationNginx rewrite(重写)一、location1、常用的Nginx 正则表达式2、location的类型3、location 的匹配规则4、location 优先级5、location 示例说明5.1只修改网页路径5.2修改nginx配置文件和网页路径5.3一般前缀5.4正则匹配5.5前缀…...
uniapp实现地图电子围栏功能
该功能使用uniapp中内置组件map实现 效果图预览: 实现过程: 1.文档: 2.代码: <template><view><map :style"width: 100%; height:screenHeight" :latitude"latitude" :longitude"longit…...
LeetCode第376场周赛
文章目录 1.Find Missing and Repeated Values2.Divide Array Into Arrays With Max Difference3.Minimum Cost to Make Array Equalindromic 1.Find Missing and Repeated Values 直接暴力过 class Solution { public:vector<int> findMissingAndRepeatedValues(vecto…...
数据仓库与数据挖掘小结
更加详细的只找得到pdf版本 填空10分 判断并改错10分 计算8分 综合20分 客观题 填空10分 判断并改错10分--错的要改 mooc中的--尤其考试题 名词解释12分 4个,每个3分 经常碰到的专业术语 简答题40分 5个,每道8分 综合 画roc曲线 …...
ensp创建配置环境,实现全网互访
文章目录 创建配置环境,实现全网互访配置步骤接入层交换机(sw4、sw5)划分vlan汇聚层交换机(sw2、sw3)配置ip地址作为vlan网关、与sw1 ip地址直连核心层交换机(sw1)配置ip地址与汇聚层交换机&…...
智能优化算法应用:基于JAYA算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于JAYA算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于JAYA算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.JAYA算法4.实验参数设定5.算法结果6.参考文献7.MA…...
ripro后台登录后转圈和图标不显示的原因及解决方法
最近,好多小伙伴使用ripro主题的小伙伴们都发现,登录后台后,进入主题设置就转圈,等待老半天后好不容易显示页面了,却发现图标不显示了,都统一显示为方框。 这是因为后台的js、css这类静态资源托管用的是js…...
android 源码编译android 12
一、python安装 python2 sudo apt-get install python python3 sudo apt-get install python3 二、repo管理多个git repo因为Android源码由多个git组成,故安装repo利于管理git工程. repo安装步骤 a.第一步, 新建一个空白文件夹保存repo引导文件,并包含你的路径…...
CSS第二天导读
1,Emmet语法 Emmet语法的前身是Zen coding,它使用缩写,来提高html / css 的编写速度,Vscode内部已经集成该语法 1.1,快速生成HTML结构语法 1.想要快速生成多个相同标签,加上*就可以了,比如 d…...
scroll-behavior属性使用方法
定义和用法: scroll-behavior 属性规定当用户单击可滚动框中的链接时,是否平滑地(具动画效果)滚动位置,而不是直线跳转。 <style>element{/* 核心代码 */scroll-behavior: smooth;} </style> 属性值&am…...
Python Django 连接 PostgreSQL 操作实例
更多Python学习内容:ipengtao.com 大家好,我是彭涛,今天为大家分享 Python Django 连接 PostgreSQL 操作实例,全文3500字,阅读大约10分钟 在Web开发中,使用Django连接到PostgreSQL数据库是一种常见的选择。…...
5.实现简化版raft协议完成选举
1.设计 前面已经完成了netty的集成,接下来就是借助netty完成选举就行了。 针对选举,我们用到了VotRequestMessage、VotRespMessage、当节点下线时NodeOfflineMessage、NodeOnlineMessage、NodeOnlineRespMessage 1.1 节点详细的交互 1.2 对所有消息的…...
服装管理系统 简单实现
服装管理系统 项目使用jsp servletmysql实现; 登陆注册 首页 首页显示服装信息 服装管理 1添加服装 2修改服装 3分页查询服装 4导出服装信息 5 导入服装信息 代码结构截图 百度网盘 链接:https://pan.baidu.com/s/1zfLHGMnrYd-JtnhzS5elYQ 提取码…...
深度学习项目实战:垃圾分类系统
简介: 今天开启深度学习另一板块。就是计算机视觉方向,这里主要讨论图像分类任务–垃圾分类系统。其实这个项目早在19年的时候,我就写好了一个版本了。之前使用的是python搭建深度学习网络,然后前后端交互的采用的是java spring …...
C#浅拷贝和深拷贝数据
目录 一、浅拷贝 二、深拷贝 一、浅拷贝 就是把原来的数据,复制一份,但是2份数据是共享地址的,修改第一份数据或者修改第二份数据,都会一起改变,这可能不是我们程序中需要的场景。 下面我们演示一下,首…...
【JVM】4.运行时数据区(程序计数器、虚拟机栈)
文章目录 4.JVM的运行时数据区4.1 程序计数器4.2 Java虚拟机栈4.3 虚拟机栈内存溢出 4.JVM的运行时数据区 4.1 程序计数器 程序计数器(PC)会记录着下一行字节码指令的地址。执行完当前指令后,PC刷新,JVM的执行引擎根据程序计数器…...
算法:程序员的数学读书笔记
目录 0的故事 一、按位计数法 二、不使用按位计数法的罗马数字 三、十进制转二进制 四、0所起到的作用 逻辑 一、为何逻辑如此重要 二、兼顾完整性和排他性 三、逻辑 四、德摩根定律 五、真值表 六、文氏图 七、卡诺图 八、逻…...
机器学习算法---时间序列
类别内容导航机器学习机器学习算法应用场景与评价指标机器学习算法—分类机器学习算法—回归机器学习算法—聚类机器学习算法—异常检测机器学习算法—时间序列数据可视化数据可视化—折线图数据可视化—箱线图数据可视化—柱状图数据可视化—饼图、环形图、雷达图统计学检验箱…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
