hdu4400 BFS+STL

题意:

煤矿爆炸,每个煤矿有自己的x,y,d,d是他爆炸后会是d距离内的爆炸,每次输入一个爆炸的煤矿,问你这个煤矿爆炸会有多少个煤矿爆炸.

思路:

爆炸的过程就是搜索的过程,被当前煤矿弄爆炸的煤矿可能继续去吧别的煤矿蹦爆炸,所以是搜索的过程,但直接搜会超时,所以各种STL,估计是数据水,不然我人感觉STL碰到坑人数据也得N^2,一样跪,思路是按照x离散化,1 2 3 3 4 离散化成1 2 3 4,然后每个点建立一个multiset,然后把y 和 id塞进去,按照y排序,像上面的那组,1 2 4的set里就一组数据,而3里面有两组,每次询问的时候,先找到x的范围,
x - d ,x + d,可以二分或者直接STL,然后再在找到的范围里找出满足条件的y,直接STL,这个地方二分会有点复杂,但如果想二分绝对可以,然后就这样广搜就行了....

#include<stdio.h>

#include<string.h>

#include<queue>

#include<set>

#include<algorithm>

#define N 100000 + 100



using namespace std;

typedef struct NODE

{

   int y ,id;

   NODE(int id_ ,int y_)

   {

      y = y_;

      id = id_;

   }

   bool operator < (const NODE &c) const

   {

        return y < c.y;

   }

}NODE; 

typedef struct

{

   int x ,y ,d;

}NOD;

int abss(int a)

{

   return a < 0 ? -a : a;

}

NOD node[N];

int X_hash[N] ,hash_n;

int mark[N];

multiset<NODE>SET[N];

int BFS(int s)

{

   int ans = 0;

   if(mark[s]) return ans;

   mark[s] = 1;

   queue<int>q;

   q.push(s);

   multiset<NODE>::iterator yl,yr,it;

   while(!q.empty())

   {

      ans ++;

      int tou ,xin;

      tou = q.front();

      q.pop();

      int xl = lower_bound(X_hash  ,X_hash + hash_n  ,node[tou].x - node[tou].d) - X_hash;

      int xr = upper_bound(X_hash  ,X_hash + hash_n  ,node[tou].x + node[tou].d) - X_hash;

      for(int i = xl ;i < xr ;i ++)

      {

         int yy = node[tou].d - abss(node[tou].x - X_hash[i]);

         yl = SET[i].lower_bound(NODE(0 ,node[tou].y - yy));

         yr = SET[i].upper_bound(NODE(0 ,node[tou].y + yy));

         for(it = yl ;it != yr ;it++)

         {

            if(!mark[it->id])

            {

               mark[it->id] = 1;

               //ans ++;

               q.push(it->id);

            }

         }

         SET[i].erase(yl ,yr);

      }

   }

   return ans;

}

int main ()

{

   int i ,j ,n ,m ,cas = 1;

   while(~scanf("%d" ,&n) && n)

   {

      for(i = 0 ;i < n ;i ++)

      {

         scanf("%d %d %d" ,&node[i].x ,&node[i].y ,&node[i].d);

         X_hash[i] = node[i].x;

      }

      sort(X_hash ,X_hash + n);

      hash_n = unique(X_hash,X_hash + n) - X_hash;

      for(i = 0 ;i < hash_n ;i ++)

      SET[i].clear();

      for(i = 0 ;i < n ;i ++)

      {

         int id = lower_bound(X_hash ,X_hash + hash_n ,node[i].x) - X_hash;

         //int xl = lower_bound(X_hash + 1 ,X_hash + hash_n + 1 ,node[tou].x - node[tou].d) - X_hash;

         SET[id].insert(NODE(i ,node[i].y));

      }

      scanf("%d" ,&m);

      printf("Case #%d:\n",cas ++);

      memset(mark ,0 ,sizeof(mark));

      for(i = 1 ;i <= m ;i ++)

      {

         int id;

         scanf("%d" ,&id);

         printf("%d\n" ,BFS(id-1));

     }

   }

   return 0;

}

巴特西

hdu4400 BFS+STL

最新文章

热门文章