当前位置: 开发笔记 > 编程语言 > 正文

试题历届试题危险系数

作者：黄宗翰琼琦莉雯 | 来源：互联网 | 2023-10-11 20:43

资源限制时间限制：1.0s 内存限制：256.0MB 问题描述抗日战争时期，冀中平原的地道战曾发挥重要作用。地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了

资源限制
时间限制：1.0s 内存限制：256.0MB

问题描述

抗日战争时期，冀中平原的地道战曾发挥重要作用。

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数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.

样例输入
7 6

1 3

2 3

3 4

3 5

4 5

5 6

1 6

样例输出
2

这题用深搜就可，先深搜判断询问的两点间是否连通（因为1 <= u, v <= n，所以令要排除测试的点为0即可判断），若连通，则一个个点做排除测试，若排除该点后可行路径数为0，那么说明这是一个关键点，危险系数df加一. 注意剪枝，一旦发现该点不是关键点，就直接终止测试.

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #define INF 0x3f3f3f3f
10 #define zero 1e-7
11
12 using namespace std;
13 typedef long long ll;
14 const ll mod=1e9+7;
15 const ll max_n=1005;
16
17 struct node {
18 int u, v;
19 }e[max_n<<1];
20
21 int n, m;//站点数，通道数
22 int su, sv;//询问的两点
23 int ans=0;//排除某点后可行的路径数
24 bool vis[max_n]={false};//标记是否访问过
25 bool flag[max_n]={false};//标记改点是否排除测试过
26
27 void dfs(int s, int del) {//源点，要排除测试的点
28 vis[s]=true;
29 for(int i=0; i30 if(e[i].u==s && !vis[e[i].v] && e[i].v!=del) {
31 if(e[i].v==sv)
32 ans++;
33 else
34 dfs(e[i].v, del);
35 }
36 if(e[i].v==s && !vis[e[i].u] && e[i].u!=del) {
37 if(e[i].u==sv)
38 ans++;
39 else
40 dfs(e[i].u, del);
41 }
42 if(ans) return;//一旦找到排除点del后仍能使询问的两点连通的路径，即del不是关键点，则直接终止测试
43 }
44 vis[s]=false;
45 }
46
47 int main() {
48 cin>>n>>m;
49 int df=0;
50 for(int i=0; i51 cin>>e[i].u>>e[i].v;
52 }
53 cin>>su>>sv;
54 dfs(su, 0);//先判断不排除任何点时，询问的两点是否连通
55 if(!ans) df=-1;//若询问的两点不连通则令df=-1
56 else {
57 for(int i=1; i<=n; i++) {
58 ans=0;
59 if(i!=su && i!=sv && !flag[i]) {
60 flag[i]=true;
61 memset(vis, false, sizeof vis);//注意要重新初始化
62 dfs(su, i);
63 if(!ans) df++;
64 }
65 }
66 }
67 cout<68 return 0;
69 }
70 /*
71 5 4
72 1 3
73 2 3
74 1 4
75 4 5
76 2 5
77
78 3
79 */

推荐阅读

char
获取当前模块所在路径的GetModuleFileName函数用法详解

本文详细介绍了GetModuleFileName函数的用法，该函数可以用于获取当前模块所在的路径，方便进行文件操作和读取配置信息。文章通过示例代码和详细的解释，帮助读者理解和使用该函数。同时，还提供了相关的API函数声明和说明。 ... [详细]

蜡笔小新 2023-12-14 19:29:57
char
电话号码的字母组合解题思路和代码示例

本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法，可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]

蜡笔小新 2023-12-14 18:50:22
char
gcdexgcd斐蜀定理的求解方法及应用

本文介绍了求解gcdexgcd斐蜀定理的迭代法和递归法，并解释了exgcd的概念和应用。exgcd是指对于不完全为0的非负整数a和b，gcd(a,b)表示a和b的最大公约数，必然存在整数对x和y，使得gcd(a,b)=ax+by。此外，本文还给出了相应的代码示例。 ... [详细]

蜡笔小新 2023-12-14 17:48:30
utf-8
Python3中选择文件对话框的格式打开和保存图片

本文介绍了在Python3中如何使用选择文件对话框的格式打开和保存图片的方法。通过使用tkinter库中的filedialog模块的asksaveasfilename和askopenfilename函数，可以方便地选择要打开或保存的图片文件，并进行相关操作。具体的代码示例和操作步骤也被提供。 ... [详细]

蜡笔小新 2023-12-14 17:46:55
io
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
io
Android开发笔记：使用Picasso加载网络图片等比例缩放

在Android开发中，使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法，并提供了具体的代码实现。通过获取图片的宽高，计算目标宽度和高度，并创建新图实现等比例缩放。 ... [详细]

蜡笔小新 2023-12-14 17:34:00
version
kotlin动画实现上下移动、放大缩小、旋转功能

本文介绍了使用kotlin实现动画效果的方法，包括上下移动、放大缩小、旋转等功能。通过代码示例演示了如何使用ObjectAnimator和AnimatorSet来实现动画效果，并提供了实现抖动效果的代码。同时还介绍了如何使用translationY和translationX来实现上下和左右移动的效果。最后还提供了一个anim_small.xml文件的代码示例，可以用来实现放大缩小的效果。 ... [详细]

蜡笔小新 2023-12-14 17:29:08
version
JetBrain有哪些产品可以用来编写C++和C代码？

本文介绍了JetBrain的哪些产品可以用来编写C++和C代码，帮助读者选择适合自己的开发工具。 ... [详细]

蜡笔小新 2023-12-14 17:23:24
char
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
char
Android 新闻App的本地服务器搭建教程

本文介绍了在开发Android新闻App时，搭建本地服务器的步骤。通过使用XAMPP软件，可以一键式搭建起开发环境，包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表，并设置相应的属性。最后，给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]

蜡笔小新 2023-12-14 17:15:19
io
brain是什么意思_brain怎么读_brain翻译_用法_发音_词组_同反义词_脑新东方在线英语词典

本文介绍了brain的意思、读音、翻译、用法、发音、词组、同反义词等内容，以及脑新东方在线英语词典的相关信息。还包括了brain的词汇搭配、形容词和名词的用法，以及与brain相关的短语和词组。此外，还介绍了与brain相关的医学术语和智囊团等相关内容。 ... [详细]

蜡笔小新 2023-12-14 16:52:33
io
云原生边缘计算之KubeEdge简介及功能特点

本文介绍了云原生边缘计算中的KubeEdge系统，该系统是一个开源系统，用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建，并为网络应用程序提供基础架构支持。同时，KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外，KubeEdge还支持跨平台工作，在私有、公共和混合云中都可以运行。同时，KubeEdge还提供数据管理和数据分析管道引擎的支持。最后，本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]

蜡笔小新 2023-12-14 16:49:01
js
PHP图片截取方法及应用实例

本文介绍了使用PHP动态切割JPEG图片的方法，并提供了应用实例，包括截取视频图、提取文章内容中的图片地址、裁切图片等问题。详细介绍了相关的PHP函数和参数的使用，以及图片切割的具体步骤。同时，还提供了一些注意事项和优化建议。通过本文的学习，读者可以掌握PHP图片截取的技巧，实现自己的需求。 ... [详细]

蜡笔小新 2023-12-14 16:44:09
char
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
stream
SpringBoot uri统一权限管理的实现方法及步骤详解

本文详细介绍了SpringBoot中实现uri统一权限管理的方法，包括表结构定义、自动统计URI并自动删除脏数据、程序启动加载等步骤。通过该方法可以提高系统的安全性，实现对系统任意接口的权限拦截验证。 ... [详细]

蜡笔小新 2023-12-14 16:11:30

黄宗翰琼琦莉雯

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章