本文主要是介绍neuq-acm预备队训练week 9 P8604 [蓝桥杯 2013 国 C] 危险系数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
抗日战争时期，冀中平原的地道战曾发挥重要作用。
题目限制
题目描述
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数 DF(x,y)：
对于两个站点 x 和 y(x!=y), 如果能找到一个站点 z，当 z 被敌人破坏后，x 和 y 不连通，那么我们称 z 为关于 x,y 的关键点。相应的，对于任意一对站点 x 和 y，危险系数 DF(x,y) 就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。
输入格式
解题思路
这题可以用dfs来解，具体看代码
AC代码
#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,ans,cnt[1010],sum;
bool b[1010],a[1010][1010];
void dfs(int N);
int main()
{scanf("%d%d",&n,&m);while(m--){scanf("%d%d",&u,&v);a[u][v]=a[v][u]=1;//无向，令u到v和v到u为1}scanf("%d%d",&u,&v);dfs(u);if(sum>0){for(int i=1;i<=n;i++)if(cnt[i]==sum) //如果这个点被走过的总次数与路径总数相等(必经点)ans++; //那么删去这个点起点与终点间一定不连通。printf("%d",ans-1); //因为终点也被算在内，所以总危险系数要减去起点的1。}elseprintf("-1"); //如果无路径连通则输出-1return 0;
}
void dfs(int N)
{if(N==v) //如果到终点{sum++; //路径总数加一for(int i=1;i<=n;i++)if(b[i]==1)cnt[i]++;//每个被走过的点，被走总次数加一}else{for(int i=1;i<=n;i++)if(a[N][i]==1&&b[i]==0)//如果未被走过{b[i]=1;//标记dfs(i);b[i]=0;//回溯}}
}这篇关于neuq-acm预备队训练week 9 P8604 [蓝桥杯 2013 国 C] 危险系数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
