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开发,免费、开源的前端地图开…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
