试题 历届试题 危险系数(c++)
程序员文章站
2022-11-08 14:07:58
思路:暴力枚举注意这是无向图, 像我的代码里面,一条边要存两次#include #include #include #include using namespace std;//最大边数const int maxe(2e3 + 5);//最大点数const int maxn(1e3 + 5);//边结构定义typedef struct Edge{ int fr...
思路:暴力枚举
注意这是无向图, 像我的代码里面,一条边要存两次
#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
//最大边数
const int maxe(2e3 + 5);
//最大点数
const int maxn(1e3 + 5);
//边结构定义
typedef struct Edge{
int from, to;
//默认是不被破坏
bool destroy;
Edge(int _from = -1, int _to = -1):from(_from), to(_to), destroy(false) {};
}Edge;
Edge es[maxe];
bool vis[maxn];
int n, m, st, en, ans;
bool BFS(int st, int en)
{
queue<int> QNode;
QNode.push(st);
while(!QNode.empty())
{
int cur_node = QNode.front();
QNode.pop();
//cout << '[' << cur_node << ']' << endl;
vis[cur_node] = true;
for (int i = 1; i <= 2 * m; i++)
{
if (es[i].from == cur_node && vis[es[i].to] == false && es[i].destroy == false)
{
//cout << "[" << es[i].from << ", " << es[i].to << "]" << endl;
if (es[i].to == en)
return true;
QNode.push(es[i].to);
vis[es[i].to] = true;
}
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
memset(vis, false, sizeof(vis));
cin >> n >> m;
for (int i = 1; i <= 2 * m; i+=2)
{
int from, to;
cin >> from >> to;
es[i].from = from;
es[i].to = to;
es[i].destroy = false;
es[i + 1].from = to;
es[i + 1].to = from;
es[i + 1].destroy = false;
}
cin >> st >> en;
if (BFS(st, en) == false) cout << -1 << endl;
else
{
ans = 0;
for (int i = 1; i <= n; i++)
{
//关键点不能是 st & en
if (i != st && i != en)
{
for (int j = 1; j <= 2 * m; j++)
{
if (es[j].from == i || es[j].to == i)
es[j].destroy = true;
}
//vis每次都要清空(初始化)
memset(vis, false, sizeof(vis));
if (BFS(st, en) == false) ans++;
//边用完了要返回到初始状态
for (int j = 1; j <= 2 * m; j++)
es[j].destroy = false;
}
}
cout << ans << endl;
}
system("pause");
return 0;
}
本文地址:https://blog.csdn.net/qq_45591813/article/details/108974115