企业建网站流程,盐城网站建设包括哪些,网页制作模板关于我们,一级a做片性视频 网站在线观看题目链接:http://acm.swust.edu.cn/problem/0085/ Time limit(ms): 5000 Memory limit(kb): 65535Description某个地区有许多城镇#xff0c;但并不是每个城镇都跟其他城镇有公路连接#xff0c;且有公路的并不都能双向行驶。现在我们把这些城镇间的公路分布及允许… 题目链接:http://acm.swust.edu.cn/problem/0085/ Time limit(ms): 5000 Memory limit(kb): 65535 Description 某个地区有许多城镇但并不是每个城镇都跟其他城镇有公路连接且有公路的并不都能双向行驶。现在我们把这些城镇间的公路分布及允许的行驶方向告诉你你需要编程解决通过公路是否可以从一个城镇到达另一个城镇。我们规定城镇自己跟自己可互相到达即A可到达A). Input 第一行只有一个数N,下面将跟着2N行数据. 在前N行数据中,对于每行数据,最开头一个数字number,表明这一行总共有number个数,number的下一个数为i,代表编号为i的那个城镇.这行余下的就是跟i有公路连接的城镇的(编号)名单且只能从城镇i驶向其他城镇。如 4 1 2 3表明:此行有4个数,跟城镇1有公路连接的城镇是编号为2和3的城镇.是从1连到2 和3 ,不能从2 和3 连到1. 在后N行数据中,每行由两个数字组成a,b(表示城镇的编号). 对于每个输入的数有如下关系 0 input_number 1000 . Output 对于输入数据中的每个a,b,判断是否可以从城镇a通过公路到达城镇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 解题思路处理好数据后直接bfs~~~ 代码如下 1 #include iostream2 #include queue3 #include cstring4 #include algorithm5 using namespace std;6 int mpt[1001][1001], vis[1001];7 int bfs(int x, int y, int n){8 queueint 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);//找出出现的点的最大值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.h2 #include string.h3 #define maxn 100014 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; imaxn; 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 转载于:https://www.cnblogs.com/zyxStar/p/4580452.html
