风险度量

Max超

发布于 2019-01-21 06:49:22

70000

代码可运行

文章被收录于专栏：蓝桥杯历年省赛真题集蓝桥杯历年省赛真题集

运行总次数：0

代码可运行

题目 X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路，构成通信网。两个空间站间可能直接通信，也可能通过其它空间站中转。

对于两个站点x和y (x != y), 如果能找到一个站点z，使得：当z被破坏后，x和y无法通信，则称z为关于x,y的关键站点。

显然，对于给定的两个站点，关于它们的关键点的个数越多，通信风险越大。

你的任务是：已知网络结构，求两站点之间的通信风险度，即：它们之间的关键点的个数。

输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，链路数。空间站的编号从1到n。通信链路用其两端的站点编号表示。接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。最后1行，两个数u,v，代表被询问通信风险度的两个站点。

输出：一个整数，如果询问的两点不连通则输出-1.

例如：用户输入： 7 6 1 3 2 3 3 4 3 5 4 5 5 6 1 6 则程序应该输出： 2 初次看到这个题，一下想到邻接矩阵，然后通过深度搜索找寻答案

#include<iostream>
#include<queue>
#define N 1000
using namespace std;
int num[N][N] = {0};
int map[N] = {0}; 
int time[N] = {0};
int x[N] = {0};
int u,v ,n,m,cnt = 0;
//构建矩阵 
void creat(int n,int m)
{
    int u , v;
    for(int i = 0; i < m; i++)
    {
        cin >> u>>v;
        num[u][v] = 1;
        num[v][u] = 1;
    }
    cout<<"所建立的矩阵为："<<endl;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1;j <= n; j++)
        {
            cout << num[i][j];
        }
        cout << endl;
    }
    return ;
}
//判断是否走回路 
int check(int n,int step)
{
    for(int i = 0;i <= step; i++)
    {
        if(n==map[i])
        {
            return 0;
        }
    }
    return 1;
}
//矩阵搜索  DFS
void DFS(int index,int step)
{
    if(index==v)
    {
        cnt++;
        for(int i = 0; i < step;i++)
        {
            time[map[i]]++;
        }
        return ;
    }
    for(int i = 1; i <= n; i++)
    {
        if(num[index][i]&&check(i,step))
        {
            map[step] = i;
            DFS(i,step+1);
            map[step] = 0; 
        }
    }
} 
int main()
{
    cin >> n>>m;
    creat(n,m);
    cin >> u >> v;
    map[0] = u;
    DFS(u,1); 
    int x = 0;
    for(int i = 1; i <= n; i++)
    {
        if(time[i]==cnt)//判读在某个站点是否是唯一数
        {
            x++;
        }
    }
    if(cnt==0)
    {
        cout << "-1";
    }
    else if(x==0)
    {
        cout << "0";
    }
    else
    {
        cout << x-2;
    }
    return 0;
}

之后查了一下其他算法，发现使用并查集特别方便。详细了解并查集请见并查集

//并查集
#include<iostream>
using namespace std;
int pre[1005];//每个点的前导点
int route[2005][2];
//可以配对的路线
int sum = 0;
//符合条件的 即关键点的数量

//查找
int find(int x)
{
    int r = x;
    while (pre[r] != r)
        r = pre[r];
    int i = x, j;
    while (i != r)//路径压缩算法
    {
        j = pre[i];//在改变他的前导点时，存储他的值
        pre[i] = r;
        i = j;//改变他的前导点为根节点
    }
    return r;
}


void join(int x, int y)
//组合
{
    int fx = find(x), fy = find(y);//分别记录x,y的根节点
    if (fx != fy)//如果他们的根节点相同，则说明他们不是连通图
        pre[fx] = fy;//将x的根结点 同 相连接
}

int main()
{
    int n, m;
    cin >> n>>m;//n表示站点的个数，m表示链路的个数

    for (int i = 0; i < m; i++)
    {
        cin >> route[i][0] >> route[i][1];
        join(route[i][0], route[i][1]);//将数据相互连接
    }


    int q1,q2;//待询问的两个点
    cin >> q1 >> q2;


    for (int ii = 0; ii < n; ii++)pre[ii] = ii;
    for (int j = 0; j < m; j++)
    {

            join(route[j][0], route[j][1]);
    }
    int a = find(q1);
    int b = find(q2);
    //如果边全部存在时不可达，则输出 -1；
    if (a != b)
    {
        cout << "-1" << endl;
    }

    else
    {
        for (int i = 1; i <= n; i++)
//枚举每一个点
        {
            if (i == q1 || i == q2)continue;
//如果是被询问的点，跳过，无需遍历   此处是最关键的部分
            for (int j = 1; j <= n; j++)pre[j] = j;
//将每一个初始化

            for (int j = 0; j < m; j++)
            {
                if (route[j][0] == i || route[j][1]==i)continue;
//去除当前点互相关联的边   解决问题的关键
                int a = find(route[j][0]);
                int b = find(route[j][1]);
                if (a > b) { a ^= b; b ^= a; a ^= b; };//交换
                if (a != b)pre[b] = a;
//以较小的点作为父节点
            }
            int a = find(q1);
            int b = find(q2);
            if (a != b)sum++;;
}