【洛谷】P8604 [蓝桥杯 2013 国 C] 危险系数（爆搜）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【洛谷】P8604 [蓝桥杯 2013 国 C] 危险系数（爆搜）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1：核心思路：

把每个点（除起点和终点）的当成关键点z试一试，每个点（当然该点还能必须直接或者间接与起点相连，不然该点本来就和起点是否到达终点无关，那么该点肯定是不能算的）都跑一遍bfs查找是否没有当前关键点z，起点还能不能到终点，如果不能，则该z就是关键点，关键点点数cnt++。

2：-1情况

另外在没有设置关键点的时候先跑一遍，如果在没有限制的情况下，还是不能到达终点，那么就输出-1。

okk上

3：ACcode:

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=2e3+10;
int mp[N][N],a[N][N],n,m,x,y,cnt;
bool vis[N];
void copy(){
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	mp[i][j]=a[i][j];
}
bool bfs(int z){
	memset(vis,false,sizeof vis);
	copy();
	queue<int>q;
	q.push(x);
	vis[x]=true;
   while(!q.empty()){
   	  int t=q.front();
   	  q.pop();
   	  for(int i=1;i<=n;i++){
   	  	  if(mp[t][i]==0||t==z||i==z||vis[i])continue;
   	  	  if(i==y) return 0;
   	  	  q.push(i);
   	  	  vis[i]=true;
		 }
   }
   return 1;
}
void solve(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
  	int u,v;
  	cin>>u>>v;
  	a[u][v]=1,a[v][u]=1;
  }
  cin>>x>>y;
  if(bfs(0)==1){
  	cout<<"-1";
  	return;
  } 
  for(int i=1;i<=n;i++){
  	if(i==x||i==y) continue;
  	if(bfs(i)) cnt++;
  }
  cout<<cnt<<"\n"; 
  
}
int main(){
	
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

over~文章来源地址https://www.toymoban.com/news/detail-603218.html

到了这里，关于【洛谷】P8604 [蓝桥杯 2013 国 C] 危险系数（爆搜）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！