P8604 [蓝桥杯 2013 国 C] 危险系数

这篇具有很好参考价值的文章主要介绍了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。

输入输出样例

输入 

7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

输出 

2

说明/提示

时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛

 解题思路

暴搜,我们可以求出所有的路径,并标记所有路径中的点,当某个点被标记的数量等于总路径数量时,这个点就为关键点文章来源地址https://www.toymoban.com/news/detail-658669.html

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
vector<int>s[N];
int f[N][N],mid[N];
bool st[N];
int x,y,k=-1,d;

void dfs(int t){
	if(t==y){
		if(k==-1)k=0;
		k++;
		for(int i=1;i<=d;i++)if(st[i])mid[i]++;
		return;
	}
	st[t]=true;     //把走过的点都标记一下,防止重复走同一个点 
	for(int i=0;i<s[t].size();i++){
		if(st[s[t][i]])continue;      //被标记,代表已经被走过了,直接跳过 
		dfs(s[t][i]);     //递归到下一层 
	}
	st[t]=false;   //回溯 
}


int main(){
	int n,m;
	cin>>n>>m;
	while(m--){
		int a,b; 
		cin>>a>>b;
		s[a].push_back(b);    //因为地道是双向的,所以要存两边 
		s[b].push_back(a);
		d=max(d,max(a,b));	  //求出最大的点,确定最后求答案时的范围 
	}
	cin>>x>>y;
	dfs(x);
	int ans=0;
	for(int i=1;i<=d;i++)if(mid[i]==k)ans++;
	cout<<ans-1<<endl;    //最终答案要减去出发点 
	return 0;
}

到了这里,关于P8604 [蓝桥杯 2013 国 C] 危险系数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (蓝桥杯每日一题)字符串排序

    本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小蓝要把一个字符串中的字母按其在字母表中的顺序排列 例如,LANQIAO 排列后为AAILNOQ 又如, GOODGOODSTUDYDAYDAYUP 排后为AADDDDDGGOOOOPSTUUYYY 请问对于以下字符串,排列之后字符串是什么? WHERETHEREISA

    2024年01月21日
    浏览(41)
  • 【C语言蓝桥杯每日一题】——排列字母

    TOC     😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话

    2023年04月09日
    浏览(47)
  • 蓝桥杯每日一题----单调栈和单调队列

    单调栈即栈内的元素是单调递减或者单调递增的,我们通过一个题目来理解。 单调栈模板题 题目描述 给出项数为 n 的整数数列 a 1 … a n a_1…a_n a 1 ​ … a n ​ 。 定义函数 f ( i ) f(i) f ( i ) 代表数列中第 i 个元素之后第一个大于 a i a_i a i ​ 的元素的下标,即 f ( i ) = m i n i

    2024年02月19日
    浏览(43)
  • 【C语言蓝桥杯每日一题】——等差数列

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2023年04月09日
    浏览(80)
  • 【蓝桥杯集训·每日一题】AcWing 3305. 作物杂交

    3305. 作物杂交 作物杂交是作物栽培中重要的一步。 已知有 N 种作物 (编号 1 至 N),第 i 种作物从播种到成熟的时间为 Ti。 作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。 如作物 A 种植时间为 5 天,作物 B 种植时间为 7 天,则 AB 杂交花费的时间为 7 天。 作

    2023年04月13日
    浏览(56)
  • 蓝桥杯每日一题002 不同子串(set用法)

    【问题描述】     一个字符串的非空子串是指字符串中长度至少为1的连续的一段字符组成的串。例如,字符串 aaab 有非空子串 a,b,aa,ab,aaa,aab,aaab,一共 7 个。 注意在计算时,只算本质不同的串的个数。 请问,字符串 0100110001010001 有多少个不同的非空子串?     

    2024年01月21日
    浏览(40)
  • 【迎战蓝桥】 算法·每日一题(详解+多解)-- day5

    🤞目录🤞 💖1. 数组中出现次数超过一半的数字 💖2. 二进制中1的个数 💖3. 替换空格 【大家好,我是 爱干饭的猿 ,如果喜欢这篇文章, 点个赞 👍, 关注一下吧, 后续会一直分享题目与算法思路 】 描述 给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长

    2023年04月08日
    浏览(40)
  • (蓝桥杯每日一题)平方末尾及补充(常用的字符串函数功能)

    能够表示为某个整数的平方的数字称为“平方数 虽然无法立即说出某个数是平方数,但经常可以断定某个数不是平方数。因为平方数的末位只可能是:0,1,4,5,6,9 这 6 个数字中的某个。所以,4325435332 必然不是平方数。 如果给你一个 2 位或 2 位以上的数字,你能根据末位的两位

    2024年01月21日
    浏览(46)
  • 力扣每日一题79:单词搜索

    给定一个  m x n  二维字符网格  board  和一个字符串单词  word  。如果  word  存在于网格中,返回  true  ;否则,返回  false  。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不

    2024年02月07日
    浏览(44)
  • 【力扣每日一题04】数组篇--搜索插入位置

    今天的题目,利用的是二分查找原理。很不幸我又没做出来,但是也很高兴发现自己的不足~ 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 示例 1: 示例 2: 示例 3: 由于官方答案我看不明

    2024年02月09日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包