P8604 [蓝桥杯 2013 国 C] 危险系数
题目背景
抗日战争时期,冀中平原的地道战曾发挥重要作用。
题目描述
地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。
我们来定义一个危险系数 DF(x,y):
对于两个站点 x 和 y(x=y), 如果能找到一个站点 z,当 z 被敌人破坏后,x 和 y 不连通,那么我们称 z 为关于 x,y 的关键点。相应的,对于任意一对站点 x 和 y,危险系数 DF(x,y) 就表示为这两点之间的关键点个数。
本题的任务是:已知网络结构,求两站点之间的危险系数。
输入格式
输入数据第一行包含 2 个整数 n(2≤n≤1000),m(0≤m≤2000),分别代表站点数,通道数。
接下来 m 行,每行两个整数 u,v(1≤u,v≤n,u=v) 代表一条通道。
最后 1 行,两个数 u,v,代表询问两点之间的危险系数 DF(u,v)。
输出格式
一个整数,如果询问的两点不连通则输出 −1−1。
输入输出样例
输入
7 6 1 3 2 3 3 4 3 5 4 5 5 6 1 6
输出
2
说明/提示
时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛
我们考虑找出所有的路线,如果一个点是关键点,则此点绝对会出现在每一条路线中,故我们在dfs的过程中记录下每个点被走过的次数。最后遍历一遍所有的点,找出和总路径数相同的点就是关键点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=4e4+10;
const int N=1e6+10;
int n,m;
vector<int> mp[1001];
int vis[1001];
int cnt[1001];
int sum;
void dfs(int cur,int e)
{if(cur==e){sum++;for(int i=1;i<=n;i++){if(vis[i]==1)cnt[i]++;}return ;}for(int i=0;i<mp[cur].size();i++){int k=mp[cur][i];if(!vis[k]){vis[k]=1;dfs(k,e);vis[k]=0;}}
}
void solve()
{cin>>n>>m;for(int i=0,x,y;i<m;i++){cin>>x>>y;mp[x].push_back(y);mp[y].push_back(x);}int s,e;cin>>s>>e;vis[s]=1;dfs(s,e);int ans=0;if(sum>0){for(int i=1;i<=n;i++){if(cnt[i]==sum)ans++;}cout<<ans-2<<endl;}elsecout<<-1<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
// cin>>t;while(t--){ solve();}return 0;
}
相关文章:
P8604 [蓝桥杯 2013 国 C] 危险系数
题目背景 抗日战争时期,冀中平原的地道战曾发挥重要作用。 题目描述 地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。 我们来定义一个危险系数 DF(x,y)&…...
Excel·VBA表格横向、纵向相互转换
如图:对图中区域 A1:M6 横向表格,转换成区域 A1:C20 纵向表格,即 B:M 列转换成每2列一组按行写入,并删除空行。同理,反向操作就是纵向表格转换成横向表格 目录 横向转纵向实现方法1转换结果 实现方法2转换结果 纵向转横…...
Leetcode-每日一题【剑指 Offer 06. 从尾到头打印链表】
题目 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例 1: 输入:head [1,3,2]输出:[2,3,1] 限制: 0 < 链表长度 < 10000 解题思路 1.题目要求我们从尾到头反过…...
LeetCode--HOT100题(22)
目录 题目描述:160. 相交链表(简单)题目接口解题思路代码 PS: 题目描述:160. 相交链表(简单) 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表…...
产品体系架构202308版
1.前言 当我们不断向前奔跑时,需要回头压实走过的路。不断扩张的同时把相应的内容沉淀下来,为后续的发展铺垫基石。 不知从何时起,产品的架构就面向了微服务/中台化/前后端分离/低代码化/分布式/智能化/运行可观测化的综合体,让…...
Linux systemctl 简单介绍与使用
在Linux下,systemctl是一个管理系统服务的命令。它提供了对systemd服务的控制和管理。 在系统中使用systemctl命令,您可以执行以下操作: 启动服务:systemctl start servicename停止服务:systemctl stop servicename重…...
恺英网络宣布:与华为鸿蒙系统展开合作,将开发多款手游
8月5日消息,恺英网络宣布旗下子公司盛和网络参加了华为开发者大会(HDC.Together)游戏服务论坛,并在华为鸿蒙生态游戏先锋合作启动仪式上进行了亮相。恺英网络表示,将逐步在HarmonyOS上开发多款游戏,利用Har…...
Vue CORS
使用Vue框架报错,客户端浏览器有CORS错误,怎么解决? 参考API Proxying During Development,可以新增或修改config/index.js下的proxyTable属性。 留意到 proxyTable的key值为/api,代表所有服务端域名都改成以/api开头…...
Godot 4 源码分析 - 文件读入编码处理
今天需要读入xml文件进行处理,结果读入一个带中文的文件时,出错了。当然程序还能运行,但编译器一直报错,而且XML解析也不正确 单步调试发现读入的内容出现乱码,具体逻辑: String FileAccess::get_as_text…...
Linux 中使用 verdaccio 搭建私有npm 服务器
安装 Node Linux中安装Node 安装verdaccio npm i -g verdaccio安装完成 输入verdaccio,出现下面信息代表安装成功,同时输入verdaccio后verdaccio已经处于运行状态,当然这种启动时暂时的,我们需要通过pm2让verdaccio服务常驻 ygiZ2zec61wsg…...
C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现
目录 前言 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的模拟实现 三、priority_queue的介绍和使用 1.priority_queue的介绍 2.priority_queue的使用 3.priority_queue的模…...
MyCat配置文件schema.xml讲解
1.MyCat配置 1.1 schema标签 如果checkSQLschema配置的为false,那么执行DB01.TB_ORDER时就会报错,必须用use切换逻辑库以后才能进行查询。 sqlMaxLimit如果未指定limit进行查询,列表查询模式默认为100,最多只查询100条。因为用mycat后默认数…...
Grafana集成prometheus(2.Grafana安装)
查找镜像 docker search grafana下载指定版本 docker pull grafana/grafana:10.0.1启动容器脚本 docker run -d -p 3000:3000 --namegrafana grafana/grafana:10.0.1查看是否启动 docker ps防火墙开启 检查防火墙3000端口是否开启 默认用户及密码 admin/admin 登录 ht…...
代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列
代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列 一、力扣647. 回文子串 题目链接 思路:对于字符串cabac,其中a,b,c,aba,cabac,都是回文子串,如果当前的字串是回文字串,那么它的字串中也会有回文…...
django 优化方式
前言 对于网站和Web APP来说,相同的类型的产品,响应速度越好,那么用户量就越高。不可否认的是,响应速度是用户黏粘性最好的方式之一,但往往不知道如何下手解决,希望这篇文章可以给予你一些思路 对于网站和…...
IDEA中怎么使用git下载项目到本地,通过URL克隆项目(giteegithub)
点击 新建>来自版本控制的项目 点击后会弹出这样一个窗口 通过URL拉取项目代码 打开你要下载的项目仓库 克隆>复制 gitee github也是一样的 返回IDEA 将刚刚复制的URL粘贴进去选择合适的位置点击克隆 下载完成...
09. Docker Compose
目录 1、前言 2、安装Docker Compose 2.1、Docker Compose版本 2.2、下载安装 3、初试Docker Compose 3.1、传统方案部署应用 3.2、使用编排部署应用 3.3、其他命令 3.3.1、ps 3.3.2、images 3.3.3、depends_on 3.3.4、scale 4、小结 1、前言 随着应用架构的不段…...
如何在shell脚本将node_modules里的文件复制一份到public文件里
项目背景:由于公司网络不连接公网,所以在绘制地图大屏项目时,需要我们将边界线数据包也部署起来,来获取边界线数据 解决方案: 1.让后端写个接口或者找个地方将数据包放到服务器即可 2.将数据包放到vue项目的public文…...
监控Redis的关键指标
Redis 也是一个对外服务,所以 Google 的四个黄金指标同样适用于 Redis。 1、延迟 在软件工程架构中,之所以选择 Redis 作为技术堆栈的一员,大概率是想要得到更快的响应速度和更高的吞吐量,所以延迟数据对使用 Redis 的应用程序至…...
Openlayers和leaflet如何选用?
在地图处理这块,Openlayers和Leaflet是非常有名的两个开源的JS框架,他们各有各的优势和劣势,对于刚刚步入此行业的开发者而言怎么选择框架呢? 作者做过一定的探索,在这里将成果分享给大家。 Openlayers 简介 Openlayers是一个基于Javacript开发,免费、开源的前端地图开…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
高抗扰度汽车光耦合器的特性
晶台光电推出的125℃光耦合器系列产品(包括KL357NU、KL3H7U和KL817U),专为高温环境下的汽车应用设计,具备以下核心优势和技术特点: 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计,确保在…...
6.计算机网络核心知识点精要手册
计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法:数据与控制信息的结构或格式,如同语言中的语法规则语义:控制信息的具体含义和响应方式,规定通信双方"说什么"同步:事件执行的顺序与时序…...
未授权访问事件频发,我们应当如何应对?
在当下,数据已成为企业和组织的核心资产,是推动业务发展、决策制定以及创新的关键驱动力。然而,未授权访问这一隐匿的安全威胁,正如同高悬的达摩克利斯之剑,时刻威胁着数据的安全,一旦触发,便可…...
