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;//回溯}}
}