zoj2913 Bus Pass ——BFS入门题

April 13, 2013
zoj BFS

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1912 题目大意：　　有很多个地区，有几条公交线经过一些地区，求出一个地区，满足，使这个地区到这些公交线上的所有公交站的距离中的最大值，最小。（这里的距离指的是两点之间的边数）思路：　　对于这些公交站中的每一个点，BFS，求出出当前点外，其他所有点到这个点的最小距离，然后对于公交站上的其他点，也进行同样地操作，不断更新所有点到公交站上的当前点的最小距离的较大值，然后遍历所有点，求出距离最小的一个点。用res1数组存储。res数组的作用是对于公交线上的每个点，BFS其他点的时候，临时存放其他点到这个公交站的最小距离，然后在与res1数组进行比较，用来更新res1数组。注意：　　visited数组，标记这个是不是被访问过，并且标记的顺序要想清楚！把这个点入队的时候就要标记它被访问了，而不是它出队的时候再标记！这是因为，如果两天点同时和一个点相邻，如果等点出队的时候在标记的话，就会产生这个点被访问两次的情况，这个问题让我纠结了一个星期……我去……

比如这种情况，Ｃ和Ａ，Ｂ同时相邻，假如：先访问Ａ，ｒｅｓ［Ｂ］　＝　ｒｅｓ［Ｃ］　＝　２，把Ａ标记，然后出队；再访问Ｂ，ｒｅｓ［Ｃ］　＝　３，Ｃ的值显然是不对的，所以，当把Ｂ，Ｃ两个点入队的时候，就把他们标记为已经访问，就可以了…… 　　做这个题目感触挺大的，首先，写代码要全神贯注，不能有一点儿疏忽，否则很容易犯那种超级难找出来的隐蔽的错误，一定要考虑明白再写；然后就是数组的下标什么的，养成好习惯，到底什么时候该从０开始，什么时候该从１开始，我觉得从１开始比较保险，因为有的时候会用到编号，比如这道题目，点的标号从１开始；最后就是思考这种题目应该如何存储题目给的信息，这个东西是看的书上的思想；　　自己写代码比看着人家的代码写感觉和收获是完全不一样的。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 10000+10;
int edge[MAX][11], res[MAX], res1[MAX], ve, pa, mz[MAX];
bool visited[MAX];
queue<int> qt;
void bfs(int id){
  res[id] = 1; qt.push(id); int te;
  visited[id] = true;
  while (!qt.empty()){
    te = qt.front();  qt.pop();
    for (int k = 1; k <= mz[te]; ++k){
      if (!visited[edge[te][k]]){
        qt.push(edge[te][k]);
        res[edge[te][k]] = max(res[edge[te][k]], res[te] + 1);
        visited[edge[te][k]] = true;
      }
    }
  }
  for (int k = 1; k <= MAX; ++k) {
    res1[k] = max(res1[k], res[k]);
  }
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj2913.in", "r", stdin);
#endif
  int t;scanf("%d", &t);
  while (t--){
    scanf("%d%d", &ve, &pa); int n;
    memset(mz, 0, sizeof(mz));
    for (int i = 1; i <= ve; ++i){
      scanf("%d", &n); scanf("%d", &mz[n]);
      for (int j = 1; j <= mz[n]; ++j){
        scanf("%d", &edge[n][j]);
      }
    }
    int id;
    for (int i = 1; i <= MAX; ++i) res1[i] = -1;
    for (int i = 1; i <= pa; ++i){
      scanf("%d", &n);
      for (int j = 1; j <= n; ++j){
        scanf("%d", &id);
        memset(visited, false, sizeof(visited));
        for (int k = 1; k <= MAX; ++k) res[k] = -1;
        bfs(id);
        for (int k = 1; k <= MAX; ++k)
          res1[k] = max(res1[k], res[k]);
      }
    }
    int fu = MAX, fid;
    for (int i = 1; i <= MAX; ++i){
      if (res1[i] != -1 && fu > res1[i]){
        fu = res1[i]; fid = i;
      }
    }
    printf("%d %d\n", fu, fid);
  }

  return 0;
}

　　不管怎么样，过程如何纠结，想了多少时间，写了多少遍，最后还是１Ａ了……

Read more