搜索
查看: 356|回复: 2

本来要发题解的,然后卡住发不了的题解。。。12144扩散 搜索题解

[复制链接]
 楼主| 发表于 2018-10-2 16:18:33 | 显示全部楼层 |阅读模式

            先看题。。。此题数据比较水(毕竟只有50*50),虽然正解是最小生成树,but求一遍距离之后迭代加深暴力dfs也能稳过(最大时间复杂度只有0.5*50*50*【50*50+连边数(dfs)】,10ms,主要是蒟蒻不会弄最小生成树啊),以下解析           1, 20%的数据直接无脑dfs/bfs扩散过不解释
           2,对于 100%数据,由于x,y坐标太大,不可能再采用1的策略(复杂度1e9不能忍),毫不处理的搜索肯定没有希望,所以需要预处理,即将无序的搜索化为有序的搜索才行。那么搜索的顺序怎么解决呢?这里考虑一下时间的顺序,即对于每一个相遇的时间节点的间隔,我们盲目的t++其实是无效操作,因为t++和t+=delta t在结果上是等效的。所以我们只需要先求一下距离(曼哈顿距离,距离详见代码),每次按照时间顺序从小到大运算(选择排序,因为必须每个进行,当然其他数据结构是可以sort的,不过这里就用简单的数组就能解决问题了)。直接扫一遍,算出当前时间的min值,将时间等于min值的两两边连上,更新节点的连线关系后,就成了裸的搜索模板。。。搜索不解释
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <cstdlib>//头文件
  5. using namespace std;
  6. long long ti[55][55];//时间
  7. int map[55][55];//联通关系
  8. int book[55];//每次dfs的标记,需要更新
  9. struct node
  10. {
  11.         int x,y;
  12. }dot[55];//节点
  13. int n;
  14. void dfs(int i)
  15. {
  16.         book[i]=1;
  17.         for(int j=1;j<=n;j++)
  18.                 if(map[i][j]==1&&i!=j&&book[j]==0)
  19.                 {
  20.                         dfs(j);
  21.                         book[j]=1;
  22.                 }
  23. }//最简单的dfs模板函数
  24. int main()//请从此阅读
  25. {
  26.         //freopen("ppg.in","r",stdin);
  27.         //freopen("ppg.out","w",stdout);
  28.         scanf("%d",&n);
  29.         for(int i=1;i<=n;i++)
  30.         {
  31.                 scanf("%d%d",&dot[i].x,&dot[i].y);
  32.         }、、输入节点
  33.         for(int i=1;i<=n;i++)
  34.                 for(int j=i+1;j<=n;j++)
  35.                 {
  36.                         long long a=abs(dot[i].x-dot[j].x)+abs(dot[i].y-dot[j].y);
  37.                         if(a%2==1) a++;
  38.                         a/=2;
  39.                         ti[i][j]=ti[j][i]=a;
  40.                 }//计算距离,此处可以画图理解
  41.         for(int o=1;o<=n;o++)
  42.         for(int p=o+1;p<=n;p++)
  43.         {
  44.         long long cntmin=1e12;
  45.         for(int i=1;i<=n;i++)
  46.                 for(int j=i+1;j<=n;j++)
  47.                         cntmin=min(cntmin,ti[i][j]);,,求最小值
  48.         for(int i=1;i<=n;i++)
  49.                 for(int j=i;j<=n;j++)
  50.                         if(ti[i][j]==cntmin)
  51.                         {
  52.                                 ti[i][j]=ti[j][i]=1e12;
  53.                                 map[i][j]=map[j][i]=1;
  54.                         }//覆盖,否则min会重复求解
  55.         for(int i=1;i<=n;i++)
  56.                 book[i]=0;、、刷新book
  57.         dfs(1);
  58.         int flag=1;
  59.         for(int i=1;i<=n;i++)
  60.                 if(book[i]==0)
  61.                                 flag=0;
  62.         if(flag==1)
  63.         {
  64.                 printf("%lld",cntmin);
  65.                 return 0;
  66.         }//cntmin即最短时间
  67.         }
  68.         return 0;
  69. }
复制代码

            

发表于 2018-10-2 16:20:59 | 显示全部楼层
收到了
大佬 orz
         
 楼主| 发表于 2018-10-2 16:21:38 | 显示全部楼层

%%%%%%%%%%%%%%%%%%%
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

广播台
特别关注
快速回复 返回顶部 返回列表