蓝桥杯2013年第四届真题-危险系数-题解(C++代码)加油！追梦人！

1139 阅读 3 评论 0 点赞

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

![](/image_editor_upload/20191021050034_16703.jpg)
	#include<bits/stdc++.h>
    using namespace std;
    int n,m;//站点数和通道数 
    int s,t;//起点，终点 
    int mp[1000][1000]={0};//建立邻接关系表 
    int vis[1000]={0};//记录此结点是否经过 
    int times[1000]={0};//存储每次经过该结点的次数 
    int node[1000]={0};//保存结点
    int ans=0;//路径数
    void dfs(int s,int x)
    {
    	if(s==t)//判定是否到达终点 
    	{
    		ans++;//路径数加1 
    		for(int i=1;i<=x;i++)//记录每一个路径所经过哪些结点的结点次数 
    			times[node[i]]++;
    	}
    	for(int i=1;i<=n;i++)//遍历n个结点 
    		if(vis[i]==0&&mp[s][i])//根据条件，判定是否进行该结点的遍历 
    		{
    			vis[i]=1;
    			node[x+1]=i;//记录该结点 
    			dfs(i,x+1);//常规深搜 
    			vis[i]=0;
    		}
    }
    int main()
    {
    	cin>>n>>m;
    	while(m--)
    	{
    		int u,v;
    		cin>>u>>v;
    		mp[u][v]=mp[v][u]=1;
    	}
    	cin>>s>>t;//此之上，均是输入数据 
    	node[1]=s;//标记s起点为1号结点 
    	vis[s]=1;//起点永远必经过的，所以直接初始化为1 
    	dfs(s,1);//深搜 
    	int Count=0;//断点数
    	for(int i=1;i<=n;i++)
    		if(ans==times[i])//路径数和经过该点的次数相等，才为必要点，否则可以绕过此点到达终点 
    			Count++;
    	cout<<Count-2<<endl;//减去起点和终点次数 
    	return 0;
    } 
	/*************************************************************************/
//天赋决定了你的上限
//努力决定了你的下限
//毅力决定了你能在这条路走多远
//加油吧！编程路上的追梦者！-----------------------------------------------Wolf

0.0分

25 人评分

本文分类：题解列表
浏览次数：1139 次浏览
发布日期：2019-10-21 16:52:36
本文链接：https://blog.dotcpp.com/a/62208

上一篇 > C语言训练-最大数问题（Java代码）
下一篇 > [编程入门]求和训练-题解(C语言代码)

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

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

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

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

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

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

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

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

评论列表共有 3 条评论

uq_86488653141 2年前回复TA

#include<iostream>
using namespace std;
int dgfound(int*yongdao1,int*yongdao2,int start,int ending,int*pathbefore,int path[100][1000],int m,int k,int*sum)
{
    if(start==ending){
        for(int j=0;j<m;j++){
            path[*sum][j]=0;
        }
        for(int jj=0;jj<k;jj++){
            path[*sum][jj]=*(pathbefore+jj);
            //cout<<"*sum,jj"<<*sum<<","<<jj<<"="<<*(pathbefore+jj)<<endl;
        }
		(*sum)++;
        return 1;
    }
    int pp=0;
    for(int i=0;i<m;i++){
        if(*(yongdao1+i)==start){
            int pan=1;
            for(int ti=0;ti<k;ti++){
                if

鼬殇 4年前回复TA

注释很详细，谢谢大佬

PRE 4年前回复TA

这个代码复杂度不是2^n吗？

蓝桥杯2013年第四届真题-危险系数-题解(C++代码)加油！追梦人！

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 3 条评论

发表评论 取消回复

评论列表共有 3 条评论

发表评论取消回复