题目描述

时间限制：1Sec ；内存限制：128MB

  • 内容：

    抗日战争时期，冀中平原的地道战曾发挥重要作用。
    地道的多个站点间有通道连接，形成了庞大的网络。
    但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
    我们来定义一个危险系数DF(x,y)：
    对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
    本题的任务是：已知网络结构，求两站点之间的危险系数。

  • 输入：

    输入数据第一行包含2个整数n(2 < = n < = 1000), m(0 < = m < = 2000),分别代表站点数，通道数；
    接下来m行，每行两个整数 u,v (1 < = u, v < = n; u != v)代表一条通道；
    最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。

    例如：

    1
    2
    3
    4
    5
    6
    7
    8
    7 6
    1 3
    2 3
    3 4
    3 5
    4 5
    5 6
    1 6

  • 输出：

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

    例如：

    1
    2

思路

将数据处理为散列表，利用D&C方法，递归函数，分而治之。

化简题目

根据题意，可将其化简为图解题：

有n个顶点、m条边，其中有u、v两顶点，求可以将u、v完全分割到两个部分的顶点的个数

例如：

在上述举例条件下

危险系数流程图

[7]是个孤儿（没有任何点与其相连），可以不用考虑

若u、v分别为[1]、[6]，则仅有去掉[3]或[5]，可将[1]、[6]分到两个不同的部分

危险系数流程图

危险系数流程图

而去掉其他顶点则达不到这个效果

此时点的数量为 2 （[3]、[5]）。

逻辑思考

符合题目要求的点都有一个共同的特性：

所有可以连通u、v两点的线路都必须经过该点

依此实现方法可以是：

  • 解出所有路线，统计各个点的数量，数量与路线数量相等的点即为一个解

解出所有解可以用广度优先算法

将数据加工为散列表：

点 与其相连的点
1 3
2 3
3 1、2、4、5
4 3、5
5 3、4、6
6 5
7 无 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int map[2000][2];//存放输入数据的数组
int listMap[1001][2002];//存放散列表的数组
int n,m;// n 站点数量 、 m 通道数量

void inList(){
    int i,j,num;
    for(i=0;i<n;i++){
        num=1;
        for(j=0;j<m;j++){
            listMap[j+1][2001]=0;
            if(map[j][0]==i+1){
                listMap[i+1][num]=map[j][1];
                num++;
            }else if(map[j][1]==i+1){
                listMap[i+1][num]=map[j][0];
                num++;
            }
        }
    listMap[i+1][0]=num-1;
    }
}

/*
 * 将输入数据转换成散列表数据(集成一个二维数组)
 * listMap[第几个站点1-1000][所有与他链接的站点1-2000];
 *    [点][0]为链接该站点的站点数量;
 *    [点][2001]为该点成功的访问次数;~即:路线中出现该点的次数
 */

路线计算：

  • 从出发点开始，遍历其相邻的点

    • 有终点，得到路线，并继续遍历
    • 无终点，依此以其相邻的点为出发点，遍历其相邻相邻的点

  • 直到遍历完所有的点

  • 遍历过程中记录该条路线途径的点（防止产生回环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int it;//现在所处的点|起始点
int to;//判断成功的点|目标点
int in[1001]={0};//储存路径的数组|到达过为1，没有到达过为0
int inMap(int it,int to,int *in){
    int i;
    int num=0;//记录该次遍历所得到的成功的线路数

    for(i=0;i<listMap[it][0];i++){//循环遍历相邻的所有点
        if(in[listMap[it][i+1]]==1){//判断曾经到达的点
            continue;
        }
        if(listMap[it][i+1]==to){//判断终点
            num++;//成功数++
        }else{//否则递归，对其相邻点调用此函数
            in[it]=1;//将现在所处的点标记为已到过
            num+=inMap(listMap[it][i+1],to,in);
            //成功数+=经过该点到达的相邻点的成功数
            in[it]=0;//返回该点后取消标记
        }
    }
    
    listMap[it][2001]+=num;
    //现在所处点的成功路线经过数量+=上述经过该点路线的成功数
    return num;
    //返回经过该点的成功路线的数量
}

整合代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
int map[2000][2];
int listMap[1001][2002];
int n,m;// n 站点 、 m 通道

void inList();
int inMap(int,int,int*);

int main()
{
    int i;
    int ined[1001]={0};
    int it,to;
    int num1=0;
    int num;

    /**********输入***********/

    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d %d",&map[i][0],&map[i][1]);
    }
    scanf("%d %d",&it,&to);

    /********数据处理*********/

    inList();//处理数据
    num = inMap(it,to,ined);//获得成功的路线数
    
    /********判断输出*********/	
    
    if(num == 0){
        printf("-1");
    }else{
        for(i=0;i<n;i++){
            if(i+1 == it){
                continue;
            }else if(listMap[i+1][2001]==num){
                num1++;
            }
        }
        printf("%d",num1);
    }

    return 0;
}

void inList(){
    int i,j,num;
    for(i=0;i<n;i++){
        num=1;
        for(j=0;j<m;j++){
            listMap[j+1][2001]=0;
            if(map[j][0]==i+1){
                listMap[i+1][num]=map[j][1];
                num++;
            }else if(map[j][1]==i+1){
                listMap[i+1][num]=map[j][0];
                num++;
            }
        }
        listMap[i+1][0]=num-1;
    }
}

int inMap(int it,int to,int *in){
    int i;
    int num=0;

    for(i=0;i<listMap[it][0];i++){
        if(in[listMap[it][i+1]]==1){//判断曾经到达的分支
            continue;
        }
        if(listMap[it][i+1]==to){//判断终点
            num++;
        }else{
            in[it]=1;
            num+=inMap(listMap[it][i+1],to,in);//增加分支
            in[it]=0;
        }
    }
    listMap[it][2001]+=num;
    
    return num;
    return 0;
}

测试日志

p.s. 分支即为顶点 #进入# $退出 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/***输入数据***/
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
/***日志***/ 
#进入1分支#
  #进入3分支#
    1为曾经到达的分支
    #进入2分支#
      3为曾经到达的分支
      $该分支2啥也没有结束2分支返回3分支，增加其num为0
    #进入4分支#
      3为曾经到达的分支
      #进入5分支#
        3为曾经到达的分支
        4为曾经到达的分支
        5前方有终点！
        返回num为1
        $结束5分支返回4分支，增加其num为1返回num为1
      $结束4分支返回3分支，增加其num为1
    #进入5分支#
      3为曾经到达的分支
      #进入4分支#
        3为曾经到达的分支
        5为曾经到达的分支
        该分支4啥也没有结束4分支返回5分支，增加其num为0
      5前方有终点！
      返回num为1
      结束5分支返回3分支，增加其num为2返回num为2
    $结束3分支返回1分支，增加其num为2返回num为2
  $结束1分支返回主函数，增加其num为2返回num为2
#遍历结束#
/*** 结果统计 ***/  
成功路线数量为2
——————————————   
分支1共有2次成功
分支2共有0次成功
分支3共有2次成功
分支4共有1次成功
分支5共有2次成功
分支6共有0次成功
分支7共有0次成功
——————————————
忽略起始点分支1后，成功经过数量为路线总数-2-的分支有 3、5
合计数目:2
/***输出数据****/
2

THE END