当前位置：首页 > news >正文

（BFS）hdoj2377-Bus Pass

news 来源：原创 2024/4/27 6:52:04

题目地址

因为最后要看的是到所有路线上的区域最大距离最小的中心点，所以可以采取遍历路线上所有的区域，对每个区域进行BFS的办法。为了更方便的在每一次BFS都遍历所有的区域，可以加一个reach数组，记录每个区域被第几站BFS过，进行过一次就将站数赋给reach。BFS时的“距离”类似于”“等距线”，一圈圈的往外面走。

 1 #include <cstdio>
 2 #include <queue>
 3 #include<cstring>
 4 #define ZMAX 10000//定义整个地区编号的最大值
 5 #define INF 100000
 6 using namespace std;
 7 int nz,nr;//number of zones地区数，number of routes路线数
 8 int mz[ZMAX];//存储第i个区域相邻的区域数
 9 int Edge[ZMAX][10];//第i个区域相邻的区域的编号
10 int res[ZMAX];//该区域到所有路线上的区域的距离的最小值
11 int cur;//“第几站”，用以界定路线上的区域，每次刷新其他区域的res的值
12 int reach[ZMAX];//记录某个区域res已经刷新到了路线上第几个区域，e.g. reach[s]==cur 表示地区s在第cur+1站已访问
13 int max(int x,int y)
14 {
15     return (x>y)?x:y;
16 }
17 void BFS(int s)//从区域s出发的BFS遍历
18 {
19     int i,a,b;
20     int val,at;//val记录层（圈）数（即“等距线”的第几层，或者说是距离），at表示当前节点
21     queue<int> q[2];//滚动队列
22     a=0,b=1,val=0;
23     if(reach[s]<cur)//这种情况表示这一站还没刷新过s这个位置
24     {
25         q[b].push(s);
26         reach[s]=cur;
27         res[s]=max(res[s],val+1);//层数是需要+1的，这样才为需要的值
28     }
29     while(!q[b].empty())
30     {
31         swap(a,b);//开始交换a、b，滚动
32         val++;//层数+1，因为之前那层的已经全部放入队列中
33         while(!q[a].empty())
34         {
35             at=q[a].front();
36             q[a].pop();
37             for(i=0;i<mz[at];i++)
38             {
39                 if(reach[Edge[at][i]]<cur)//看这个的临近区域，未刷新就放入队列
40                 {
41                     q[b].push(Edge[at][i]);
42                     reach[Edge[at][i]]=cur;
43                     res[Edge[at][i]]=max(res[Edge[at][i]],val+1);//进行刷新
44                 }
45             }
46         }
47     }
48 }
49 int main()
50 {
51     int T;
52     int i,j,t;
53     int id;
54     int mr;//公交线路途径区域数
55     int ret,center;//记录最小星形阈值和中心地区编号
56     scanf("%d",&T);
57     for(t=0;t<T;t++)
58     {
59         memset(reach,-1,sizeof(reach));//reach要初始化为1，因为cur初始为0
60         memset(res,0,sizeof(res));
61         cur=0;
62         scanf("%d%d",&nz,&nr);
63         for(i=0;i<nz;i++)
64         {
65             scanf("%d",&id);
66             scanf("%d",&mz[id]);
67             for(j=0;j<mz[id];j++)
68                 scanf("%d",&Edge[id][j]);
69         }
70         for(i=0;i<nr;i++)
71         {
72             scanf("%d",&mr);
73             for(j=0;j<mr;j++)
74             {
75                 scanf("%d",&id);
76                 BFS(id);//对公交线路上的每个区域分别进行DFS，刷新其他所有区域的res
77                 cur++;//下一站
78             }
79         }
80         ret=10000000,center=-1;
81         for(i=0;i<10000;i++)
82         {
83             if(reach[i]==cur-1&&res[i]<ret)//第一条判断是否经过了最后一次的刷新
84             {
85                 ret=res[i];
86                 center=i;
87             }
88         }
89         printf("%d %d\n",ret,center);
90     }
91     return 0;
92 }