欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

试题 历届试题 危险系数(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

相关标签: c++ bfs