?

題目鏈接:http://acm.swust.edu.cn/problem/0085/

Time limit(ms): 5000　　　　　　Memory limit(kb): 65535 ? Description

某個地區(qū)有許多城鎮(zhèn)，但并不是每個城鎮(zhèn)都跟其他城鎮(zhèn)有公路連接，且有公路的并不都能雙向行駛。現(xiàn)在我們把這些城鎮(zhèn)間的公路分布及允許的行駛方向告訴你，你需要編程解決通過公路是否可以從一個城鎮(zhèn)到達另一個城鎮(zhèn)。（我們規(guī)定，城鎮(zhèn)自己跟自己可互相到達，即A可到達A).

?

Input

第一行只有一個數(shù)N,下面將跟著2N行數(shù)據(jù). 在前N行數(shù)據(jù)中,對于每行數(shù)據(jù),最開頭一個數(shù)字number,表明這一行總共有number個數(shù),number的下一個數(shù)為i,代表編號為i的那個城鎮(zhèn).這行余下的就是跟i有公路連接的城鎮(zhèn)的(編號)名單，且只能從城鎮(zhèn)i駛向其他城鎮(zhèn)。如 4 1 2 3，表明:此行有4個數(shù),跟城鎮(zhèn)1有公路連接的城鎮(zhèn)是編號為2和3的城鎮(zhèn).是從1連到2 和3 ,不能從2 和3 連到1. 在后N行數(shù)據(jù)中,每行由兩個數(shù)字組成a,b(表示城鎮(zhèn)的編號). 對于每個輸入的數(shù)有如下關(guān)系 0 <= input_number <= 1000 .

Output

對于輸入數(shù)據(jù)中的每個a,b,判斷是否可以從城鎮(zhèn)a通過公路到達城鎮(zhèn)b,如果可以,輸出Yes;否則輸出No.

?

Sample Input

3 4 1 2 3 3 4 5 3 5 8 1 2 1 8 4 8

Sample Output

Yes No Yes

解題思路：處理好數(shù)據(jù)后直接bfs~~~ 代碼如下： 1 #include <iostream> 2 #include <queue> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 int mpt[1001][1001], vis[1001]; 7 int bfs(int x, int y, int n){ 8 queue<int> Q; 9 Q.push(x); 10 while (!Q.empty()){ 11 int now = Q.front(); 12 Q.pop(); 13 if (now == y) return 1; 14 for (int i = 0; i < n; i++){ 15 if (!vis[i] && mpt[now][i]){ 16 vis[i] = 1; 17 Q.push(i); 18 } 19 } 20 } 21 return 0; 22 } 23 int main(){ 24 int n, t, x, y, i, j, maxn = -1; 25 cin >> t; 26 for (i = 0; i < t; i++){ 27 cin >> n >> x; 28 for (j = 0; j < n - 2; j++){ 29 cin >> y; 30 mpt[x][y] = 1; 31 maxn = max(maxn, max(x, y) + 1);//找出出現(xiàn)的點的最大值+1,避免大范圍搜索不必要的點 32 } 33 } 34 for (i = 0; i < t; i++){ 35 memset(vis, 0, sizeof(vis)); 36 cin >> x >> y; 37 cout << (bfs(x, y, maxn) ? "Yes\n" : "No\n"); 38 } 39 return 0; 40 } View Code

?

以前有個代碼，個人感覺沒問題，但是一直Rutime Error,有大神路過給個原因吧~~~

代碼如下：

1 #include <stdio.h> 2 #include <string.h> 3 #define maxn 10001 4 int map[maxn][maxn], max; 5 int dfs(int star, int next) 6 { 7 int i, flag, vis[maxn]; 8 memset(vis, 0, sizeof(vis)); 9 vis[star] = 1; 10 if (map[star][next] == 1) 11 return 1; 12 for (i = 1, flag = 0; i <= max&&!flag; i++) 13 { 14 if (vis[i] == 0 && map[star][i] == 1) 15 { 16 vis[i] = 1; 17 flag = dfs(i, next); 18 vis[i] = 0; 19 } 20 } 21 return flag; 22 } 23 int main() 24 { 25 int i, j, m, n; 26 int star, next; 27 scanf("%d", &n); 28 memset(map, 0, sizeof(map)); 29 for (i = 0; i<maxn; i++) 30 map[i][i] = 1; 31 max = 0; 32 for (i = 1; i <= n; i++) 33 { 34 scanf("%d%d", &m, &star); 35 if (star> max) 36 max = star; 37 for (j = 1; j <= m - 2; j++) 38 { 39 scanf("%d", &next); 40 if (next > max) 41 max = next; 42 map[star][next] = 1; 43 } 44 } 45 for (i = 1; i <= n; i++) 46 { 47 scanf("%d%d", &star, &next); 48 if (dfs(star, next)) 49 printf("YES\n"); 50 else 51 printf("NO\n"); 52 } 53 return 0; 54 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/zyxStar/p/4580452.html

總結(jié)

以上是生活随笔為你收集整理的[Swust OJ 85]--单向公路(BFS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。