试题历届试题危险系数(c++)

柔光的暖阳◎ 2022-12-13 01:36 311阅读 0赞

思路：暴力枚举  
注意这是无向图， 像我的代码里面，一条边要存两次

#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;
    }