九度oj 题目1495：关键点

题目描述：: 在一个无权图中，两个节点间的最短距离可以看成从一个节点出发到达另一个节点至少需要经过的边的个数。
同时，任意两个节点间的最短路径可能有多条，使得从一个节点出发可以有多条最短路径可以选择，并且沿着这些路径到达目标节点所经过的边的个数都是一样的。
但是在图中有那么一些特殊的节点，如果去除这些点，那么从某个初始节点到某个终止节点的最短路径长度要么变长，要么这两个节点变得不连通。这些点被称为最短路径上的关键点。
现给定一个无权图，以及起始节点和终止节点，要求输出该图上，这对节点间最短路径上的关键点数目。

输入：: 输入包含多组测试数据，每组测试数据第一行为4个整数n（1<=n<=10000），m(1<=m<=100000)，s(1<=s<=n)，t(1<=t<=n)。分别代表该图中的节点个数n，边数量m，起始节点s，终止节点t。
接下去m行描述边的信息，每行两个整数a，b（1<=a,b<=n 且 a != b）。表示节点a和节点b之间有一条边。

输出：: 对于每组测试数据，输出给定的这对节点间最短路径上的关键点数目。注意：若给定两个节点间不连通，则我们认为其关键点数目是0。

样例输入：

样例输出：

1
0

开始看到这个题觉得有些懵，
一开始用深度优先搜索来做，找到最短的那条路径，并且对路径上走过的每一个点进行计数
最后计数值和终点的计数值一致的点就是关键点
代码如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <iostream>
 6 #define POINT_CNT 10020
 7 
 8 using namespace std;
 9 
10 vector <int> adj[POINT_CNT];
11 int flag[POINT_CNT];
12 int cnt[POINT_CNT];
13 int path[POINT_CNT];
14 int tm[POINT_CNT];
15 int n, m, s, t;
16 int minStep;
17 
18 void dfs(int from, int step) {
19     if (step > tm[from]) {
20         return;
21     }
22     if (from != s && step == tm[from]) {
23         if (cnt[from] != 0) {
24             for (int j = 1; j <= minStep; j++) {
25                 cnt[path[j]]++;
26                 tm[path[j]] = j;
27             }
28         }
29         return;
30     }
31     if (from == t) {
32         if (step < minStep) {
33             memset(cnt, 0, sizeof(cnt));
34             for (int j = 1; j <= step; j++) {
35                 cnt[path[j]] = 1;
36                 tm[path[j]] = j;
37             }
38             minStep = step;
39         }
40         else if (step == minStep) {
41             for (int j = 1; j <= step; j++) {
42                 cnt[path[j]]++;
43                 tm[path[j]] = j;
44             }
45         }
46         return;
47     }
48     int sz = adj[from].size();
49     for (int i = 0; i < sz; i++) {
50         int p = adj[from][i];
51         if (flag[p] == 0) {
52             flag[p] = 1;
53             path[step + 1] = p;
54             dfs(p,step+1);
55             flag[p] = 0;
56         }
57     }
58 }
59 
60 int main() {
61     //freopen("input.txt", "r", stdin);
62     //freopen("output.txt", "w", stdout);
63     
64     while (scanf("%d %d %d %d", &n, &m, &s, &t) != EOF) {
65         for (int i = 0; i < POINT_CNT; i++) {
66             adj[i].clear();
67         }
68         while (m--) {
69             int a, b;
70             scanf("%d %d", &a, &b);
71             adj[a].push_back(b);
72             adj[b].push_back(a);
73         }
74         memset(flag, 0, sizeof(flag));
75         memset(cnt, 0, sizeof(cnt));
76         for (int i = 0; i <= n; i++) {
77             tm[i] = POINT_CNT;
78         }
79         minStep = POINT_CNT;
80 
81         flag[s] = 1;
82         path[0] = s;
83         tm[s] = 0;
84         dfs(s,0);
85         int way = cnt[t];
86         int ans = 0;
87         if (way == 0) {
88             puts("0");
89             continue;
90         }
91         for (int i = 1; i <= n; i++) {
92             if (cnt[i] == way && i != t) {
93                 ans++;
94             }
95         }
96         printf("%d\n", ans);
97     }
98     return 0;
99 }

中间又做了一些剪枝的处理，但提交了好几次均超时。

无奈之下考虑广度优先搜索的思路

主要问题是如何找到关键点，此处我们需要遍历两次

第一次从源点s遍历到终点t,记录每一个经过点的层数

第二次从终点t遍历到起点s,只遍历那些层数比其小的。当队列为空时那个出队列的点就是关键点。

但一开始提交又是错误

代码如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <iostream>
 6 #include <queue>
 7  
 8 #define POINT_CNT 10020
 9  
10 using namespace std;
11  
12 vector <int> edge[POINT_CNT];
13 int flag[POINT_CNT];
14 int level[POINT_CNT];
15 int n, m, s, t;
16 int minStep;
17 queue <int> que;
18  
19 int main() {
20     //freopen("input.txt", "r", stdin);
21     //freopen("output.txt", "w", stdout);
22  
23     while (scanf("%d %d %d %d", &n, &m, &s, &t) != EOF) {
24         for (int i = 0; i < POINT_CNT; i++) {
25             edge[i].clear();
26         }
27         while (m--) {
28             int a, b;
29             scanf("%d %d", &a, &b);
30             edge[a].push_back(b);
31             edge[b].push_back(a);
32         }
33         if (n == 1) {
34             puts("0");
35             continue;
36         }
37         memset(flag, 0, sizeof(flag));
38         memset(level, 0, sizeof(level));
39         while (!que.empty()) {
40             que.pop();
41         }
42         que.push(s);
43         flag[s] = 1;
44         while (!que.empty()) {
45             int p = que.front(); que.pop();
46             int ps = edge[p].size();
47             int step = level[p];
48  
49             if (p == t) {
50                 break;
51             }
52             for (int i = 0; i < ps; i++) {
53                 int to = edge[p][i];
54                 if (flag[to] == 0) {
55                     que.push(to);
56                     level[to] = step + 1;
57                     flag[to] = 1;
58                 }
59             }
60         }
61  
62         while (!que.empty()) {
63             que.pop();
64         }
65         que.push(t);
66         int ans = 0;
67         while (!que.empty()) {
68             int p = que.front(); que.pop();
69             int ps = edge[p].size();
70             int step = level[p];
71             if (p == s) {
72                 break;
73             }
74             if (que.empty()) {
75                 ans++;
76             }
77             for (int i = 0; i < ps; i++) {
78                 int to = edge[p][i];
79                 if (level[to] < step) {
80                     que.push(to);
81                 }
82             }
83         }
84         printf("%d\n", ans-1);
85     }
86     return 0;
87 }

此时考虑特殊情况，如果只有一个点怎么办？如果有重边怎么办？

一是输出0，二是增加标记是否访问过

修改代码如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <iostream>
 6 #include <queue>
 7  
 8 #define POINT_CNT 10020
 9  
10 using namespace std;
11  
12 vector <int> edge[POINT_CNT];
13 int flag[POINT_CNT];
14 int level[POINT_CNT];
15 int n, m, s, t;
16 int minStep;
17 queue <int> que;
18  
19 int main() {
20     //freopen("input.txt", "r", stdin);
21     //freopen("output.txt", "w", stdout);
22  
23     while (scanf("%d %d %d %d", &n, &m, &s, &t) != EOF) {
24         for (int i = 0; i < POINT_CNT; i++) {
25             edge[i].clear();
26         }
27         while (m--) {
28             int a, b;
29             scanf("%d %d", &a, &b);
30             edge[a].push_back(b);
31             edge[b].push_back(a);
32         }
33         if (n == 1) {
34             puts("0");
35             continue;
36         }
37         memset(flag, 0, sizeof(flag));
38         memset(level, 0, sizeof(level));
39         while (!que.empty()) {
40             que.pop();
41         }
42         que.push(s);
43         flag[s] = 1;
44         while (!que.empty()) {
45             int p = que.front(); que.pop();
46             int ps = edge[p].size();
47             int step = level[p];
48  
49             if (p == t) {
50                 break;
51             }
52             for (int i = 0; i < ps; i++) {
53                 int to = edge[p][i];
54                 if (flag[to] == 0) {
55                     que.push(to);
56                     level[to] = step + 1;
57                     flag[to] = 1;
58                 }
59             }
60         }
61  
62         while (!que.empty()) {
63             que.pop();
64         }
65         que.push(t);
66         int ans = 0;
67         memset(flag, 0, sizeof(flag));
68         flag[t] = 1;
69         while (!que.empty()) {
70             int p = que.front(); que.pop();
71             int ps = edge[p].size();
72             int step = level[p];
73             if (p == s) {
74                 break;
75             }
76             if (que.empty()) {
77                 ans++;
78             }
79             for (int i = 0; i < ps; i++) {
80                 int to = edge[p][i];
81                 if (level[to] < step && flag[to]==0) {
82                     que.push(to);
83                     flag[to] = 1;
84                 }
85             }
86         }
87         printf("%d\n", ans-1);
88     }
89     return 0;
90 }

提交，还是错误。

。。。。。。。。。。

。。。。。。。。。。。。。。。。

。。。。。。。。。。。。。。。。。。

。。。。。。。。。。。。。。。。。。。。

。。。。。。。。。。。。。。。。。。。。。。

总是不过真是令人无奈

偶然发现自己初始化 level为0

那么有些和终点相连却并不和起点相连的点就会被访问，导致错误

比如

6就会被访问

再次修改如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <iostream>
 6 #include <queue>
 7 
 8 #define POINT_CNT 10020
 9 
10 using namespace std;
11 
12 vector <int> edge[POINT_CNT];
13 int flag[POINT_CNT];
14 int level[POINT_CNT];
15 int n, m, s, t;
16 int minStep;
17 queue <int> que;
18 
19 int main() {
20     //freopen("input.txt", "r", stdin);
21     //freopen("output.txt", "w", stdout);
22 
23     while (scanf("%d %d %d %d", &n, &m, &s, &t) != EOF) {
24         for (int i = 0; i < POINT_CNT; i++) {
25             edge[i].clear();
26         }
27         while (m--) {
28             int a, b;
29             scanf("%d %d", &a, &b);
30             edge[a].push_back(b);
31             edge[b].push_back(a);
32         }
33         memset(flag, 0, sizeof(flag));
34         fill(level, level + POINT_CNT, POINT_CNT);
35         while (!que.empty()) {
36             que.pop();
37         }
38         que.push(s);
39         level[s] = 0;
40         flag[s] = 1;
41         while (!que.empty()) {
42             int p = que.front(); que.pop();
43             int ps = edge[p].size();
44             int step = level[p];
45 
46             if (p == t) {
47                 break;
48             }
49             for (int i = 0; i < ps; i++) {
50                 int to = edge[p][i];
51                 if (flag[to] == 0) {
52                     que.push(to);
53                     level[to] = step + 1;
54                     flag[to] = 1;
55                 }
56             }
57         }
58 
59         while (!que.empty()) {
60             que.pop();
61         }
62         que.push(t);
63         int ans = 0;
64         memset(flag, 0, sizeof(flag));
65         flag[t] = 1;
66         while (!que.empty()) {
67             int p = que.front(); que.pop();
68             int ps = edge[p].size();
69             int step = level[p];
70             if (p == s) {
71                 break;
72             }
73             if (que.empty()) {
74                 ans++;
75             }
76             for (int i = 0; i < ps; i++) {
77                 int to = edge[p][i];
78                 if (level[to] < step && flag[to]==0) {
79                     que.push(to);
80                     flag[to] = 1;
81                 }
82             }
83         }
84         printf("%d\n", max(ans-1,0));
85     }
86     return 0;
87 }

提交终于通过了，

汗！！！！！！！！！！！！！！！！！！

九度oj 题目1495：关键点

推荐阅读