网站建设服务上海,微信公众号怎么创建步骤,成都武侯区建设局门户网站,浙江网站开发题目背景
抗日战争时期#xff0c;冀中平原的地道战曾发挥重要作用。
题目限制 题目描述
地道的多个站点间有通道连接#xff0c;形成了庞大的网络。但也有隐患#xff0c;当敌人发现了某个站点后#xff0c;其它站点间可能因此会失去联系。
我们来定义一个危险系数 DF…题目背景
抗日战争时期冀中平原的地道战曾发挥重要作用。
题目限制 题目描述
地道的多个站点间有通道连接形成了庞大的网络。但也有隐患当敌人发现了某个站点后其它站点间可能因此会失去联系。
我们来定义一个危险系数 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(sum0){for(int i1;in;i)if(cnt[i]sum) //如果这个点被走过的总次数与路径总数相等(必经点)ans; //那么删去这个点起点与终点间一定不连通。printf(%d,ans-1); //因为终点也被算在内所以总危险系数要减去起点的1。}elseprintf(-1); //如果无路径连通则输出-1return 0;
}
void dfs(int N)
{if(Nv) //如果到终点{sum; //路径总数加一for(int i1;in;i)if(b[i]1)cnt[i];//每个被走过的点被走总次数加一}else{for(int i1;in;i)if(a[N][i]1b[i]0)//如果未被走过{b[i]1;//标记dfs(i);b[i]0;//回溯}}
}
