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

题目背景

抗日战争时期，冀中平原的地道战曾发挥重要作用。

题目描述

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数 $DF(x,y)$：

对于两个站点 $x$ 和 $y(x\ne y),$ 如果能找到一个站点 $z$，当 $z$ 被敌人破坏后，$x$ 和 $y$ 不连通，那么我们称 $z$ 为关于 $x,y$ 的关键点。相应的，对于任意一对站点 $x$ 和 $y$，危险系数 $DF(x,y)$ 就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

输入格式

输入数据第一行包含 $2$ 个整数 $n(2\le n\le 1000)$，$m(0\le m\le 2000)$，分别代表站点数，通道数。

接下来 $m$ 行，每行两个整数 $u,v(1\le u,v\le n,u\ne v)$ 代表一条通道。

最后 $1$ 行，两个数 $u,v$，代表询问两点之间的危险系数 $DF(u,v)$。

输出格式

一个整数，如果询问的两点不连通则输出 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

2

提示

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

1 -> 2 -> 3 -> 4 -> 5

1 -> 2 -> 4 -> 5

其中除去 $1$ , $5$ 有 $2$ 和 $4$ 两个点被经过两次，所以 $2$ 和 $4$为关于 $1$ 和 $5$ 的关键点，危险系数为 $2$。

• 另外，最后统计被经过的次数与总路径条数相等的点得个数时，起点 $u$ 和终点 $v$ 不计算在内。

代码注释：

$n$, $m$, $u$, $v$ 如题面， $ans$ 存危险系数， $cnt$ 为dfs时记录这个点被走过的总次数， $sum$ 为路径总数 。

$a$ 为邻接矩阵，存连通情况， $1$ 为连通，也可以使用 vector 邻接表来存储 ； $bj$( $biaoji$) 为 dfs 时记录这个点是否被走过的 。

代码：

#include<bits/stdc++.h>
#define LL long long
#define made return
#define in 0
#define China ;
using namespace std;
LL n,m,u,v,ans,cnt[1010],sum;
bool bj[1010],a[1010][1010];
void dfs(LL now){
	if(now==v){//如果走到终点了， 
		sum++;//路径总数加一。 
		for(int i=1;i<=n;i++)
			if(bj[i]==1)cnt[i]++;//每个被走过的点，被走总次数加一 
	}
	else{
		for(int i=1;i<=n;i++)
			if(a[now][i]==1&&bj[i]==0){//如果两点连通且下一步要走到的点未被走过， 
				bj[i]=1;//标记。
				dfs(i);
				bj[i]=0;//回溯一步。 
			}
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	while(m--){
		scanf("%lld%lld",&u,&v);
		a[u][v]=a[v][u]=1;//输入邻接矩阵。因为是无向的，所以u到v和v到u都要设为1。 
	}
	scanf("%lld%lld",&u,&v);
	dfs(u);
	if(sum>0){//dfs求解
		for(int i=1;i<=n;i++)
			if(cnt[i]==sum)ans++;//如果这个点被走过的总次数与路径总数相等，那么删去这个点起点与终点间一定不连通。 
		printf("%lld",ans-1);//因为起点也被算在内，所以总危险系数要减去起点的1。 
	}
	else printf("-1");//如果询问的两点无路径连通则输出'-1'。
	made in China 
}
//made in China. 中国制造。