[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs

1045 阅读 5 评论 0 点赞

原题链接：蓝桥杯2013年第四届真题-危险系数

这是样例的连通图：
![](/image_editor_upload/20200216112158_52245.png)
解题思路:
1.计算能成功到达终点的路径有多少条
2.记录每次成功到达终点经过的点
3.哪个点的经过次数=成功路径数。那么它就是关键点
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> vec[1005];	//用于记录每个站点连通的站点,不知道STL的话看作二维数组就好了 
int vis[1005];	//用于记录站点是否访问过 
int count=0;	//用于记录关键点的个数
int success_load=0;	//用于记录能成功到达的路径条数
int pass_by[1005];//用于记录全部成功路径路过某点的次数 
int u,v;	//起点,终点
int n,m; 
void dfs(int now)
{
	vis[now]=1;	//标记走过的点
	if(now==v)	//出口 
	{
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==1)	pass_by[i]++;
		}
		success_load++;
		vis[now]=0;	//注意必须对对终点清零,如果不清零,下次再找终点,因为被标记过就走不进来了 
		return;
	} 
	for(int i=0;i<vec[now].size();i++) 
	{
		if(vis[vec[now][i]]==0)	//如果准备走的点没有被标记过,那么尝试走下去 
		{
			dfs(vec[now][i]);
		}
	}
	vis[now]=0;
}
int main(int argc, char** argv)
{
	cin >> n >> m;
	int a,b;
	for(int i=0;i<m;i++)
	{
		cin >> a >> b;
		vec[a].push_back(b);	//a与b连通，所以将与a站点连通的站点存入数组 
		vec[b].push_back(a);	//这是无向图，同理b也与a连通 
	}
	cin >> u >> v;	//读入起点,终点 
	dfs(u);//dfs的参数是当前的位置,从起点开始搜索，故传入起点的位置 
	for(int i=1;i<=n;i++)
	{
		if(pass_by[i]==success_load && i!=u && i!=v)	
		count++;
	}
	if(success_load==0)	cout << "-1" << endl; 
	else	cout << count << endl;
	return 0;
}
```

0.0分

14 人评分

本文分类：题解列表
浏览次数：1045 次浏览
发布日期：2020-02-16 23:33:59
本文链接：https://blog.dotcpp.com/a/66322

上一篇 > [编程入门]求和训练-题解(Java代码)
下一篇 > [编程入门]水仙花数判断-题解(Java代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs

评论列表共有 5 条评论

发表评论取消回复

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

评论列表共有 5 条评论

发表评论取消回复