蒙奇D路飞

用户名：JackBoe

访问量：3513

签　名：

等　　级
排　　名	20085
经　　验	658
参赛次数	0
文章发表	1
年　　龄	20
在职情况	学生
学　　校	三峡大学
专　　业	计算机科学与技术

　　自我简介：

我要冲击蓝桥杯

TA的其他文章

蓝桥杯2013年第四届真题-危险系数-题解（C语言代码）
浏览：3163

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （Java代码）

蓝桥杯2013年第四届真题-危险系数-题解（C语言代码）

　　作者: 蒙奇D路飞　　　　发表时间：2020-10-26 10:55:45 浏览：3163　|　评论：2　

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

##题目 1433: [蓝桥杯][2013年第四届真题]危险系数
#### 题目链接
[危险系数](https://www.dotcpp.com/oj/problem1433.html "危险系数")

#### 解题思路:
(1)数据结构：邻接矩阵, 定义map[n+1][n+1],若果i和j相通，则使map[i][j] = 1 且 map[j][i] = 1;否则都为0
(2)核心算法：DFS深度搜索，简称深搜、DFS
(3)关键技巧：每个关键点被访问的次数(访问了这个点后且能到达终点才算一次)和所有可行路径的总数相等；全局变量使用

#### 注意事项:
(1)起点和终点不能算关键点；
(2)两站点不相通时输出-1；

#### 参考代码

```c
#include <stdio.h>
#include <stdlib.h>

int map[1001][1001]={0};//邻接矩阵，i和j连通则map[i][j] == 1,否则为0

int visited[1001];//判断节点是否被访问过 ，为1表示被访问过，否则为0

int times[1001] = {0};//记录节点被所有可行路径访问的次数

int node[1001] = {0};//存储某一条路径上访问的节点，不包括起点

int ans = 0;//路径总数

void DFS(int pos1, int pos2, int n, int t){
	if(pos1 == pos2){
		ans++;//走到了终点则路径加一条 
		for(int i = 1; i<t; i++){
			times[node[i]]++;//将这条可行路径上每一个点访问的次数+1 
		}
	}
	for(int i = 1; i<=n; i++){
		if(map[pos1][i] == 1 && visited[i]==0){
			visited[i] = 1;//仅使当前要走的这条路后面不经过i节点
			visited[pos1] = 1;
			node[t] = i;/*将i存进这条路径经过的点的数组，如果这条路不通，就会回溯，t值将会回减，不可行的节点node[t]会被更新 */
			DFS(i,pos2,n,t+1);
			visited[i] = 0;
			/*因为用到的是深搜，一条路走到底，但是从i之前某个点上可能还有其它可行的分路，这些可行的分路可能也会经过i，题目要求我们要遍历所有可行的分路，所以要将visited[i]重新设为零，使其他分路也有机会访问i节点 */
		}
	}
}

int main(){
	int n,m,pos1,pos2,count = 0;
	//pos1，pos2代表两个点值 
	scanf("%d%d",&n,&m);
	for(int i = 1; i<=m; i++){//连通地道 
		scanf("%d%d",&pos1, &pos2);
		map[pos1][pos2] = 1;
		map[pos2][pos1] = 1;
	}
	scanf("%d%d",&pos1, &pos2);
	DFS(pos1,pos2,n,1);//深搜
	//pos1和pos2分别是起点和终点，n是站点总数，1用来传给参数t 
	if(ans == 0){//pos1和pos2如果不通，直接打印-1； 
		printf("-1");
		return 0; 
	}
	for(int i = 1; i<=n; i++){
		if(times[i]==ans && i!=pos1 && i!=pos2){
//当i节点被经过且能到达终点的次数等于可行路径数时，i就是关键点
//且i不为起点和终点 
			count++;//危险系数+1 
		}
	}
	printf("%d",count);//输出危险系数 
	return 0;
}

```

0.0分

36 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

Arkkaz

假如 1 2, 1 3, 2 4, 3 4这么连接 求1 4的关键点通过次数和总路线数不等啊

2022-07-27 16:21:12

BrAnT.Gy

请问怎么才能执行到visited[i] = 0;呢

2021-03-13 16:30:20

蒙奇D路飞

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （Java代码）

【蟠桃记】（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-字符串正反连接（C语言代码）

蓝桥杯2013年第四届真题-危险系数-题解（C语言代码）

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

打水问题（C语言代码）

【简单计算】（C语言代码）

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

WU-printf基础练习2 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言训练-字符串正反连接（C语言代码）

众数问题（C语言代码）

蒙奇D路飞

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （Java代码）

【蟠桃记】 （C语言代码）

【偶数求和】 （C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

蓝桥杯2013年第四届真题-危险系数-题解（C语言代码）

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

打水问题 （C语言代码）

【简单计算】 （C语言代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

WU-printf基础练习2 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

众数问题 （C语言代码）

【蟠桃记】（C语言代码）

【偶数求和】（C语言代码）记得sum的归零时机

C语言训练-字符串正反连接（C语言代码）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

打水问题（C语言代码）

【简单计算】（C语言代码）

众数问题（C语言代码）

C二级辅导-温度转换（C语言代码）

C语言训练-字符串正反连接（C语言代码）

众数问题（C语言代码）