先看题。。。此题数据比较水(毕竟只有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值的两两边连上,更新节点的连线关系后,就成了裸的搜索模板。。。搜索不解释
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstdlib>//头文件
- using namespace std;
- long long ti[55][55];//时间
- int map[55][55];//联通关系
- int book[55];//每次dfs的标记,需要更新
- struct node
- {
- int x,y;
- }dot[55];//节点
- int n;
- void dfs(int i)
- {
- book[i]=1;
- for(int j=1;j<=n;j++)
- if(map[i][j]==1&&i!=j&&book[j]==0)
- {
- dfs(j);
- book[j]=1;
- }
- }//最简单的dfs模板函数
- int main()//请从此阅读
- {
- //freopen("ppg.in","r",stdin);
- //freopen("ppg.out","w",stdout);
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d%d",&dot[i].x,&dot[i].y);
- }、、输入节点
- for(int i=1;i<=n;i++)
- for(int j=i+1;j<=n;j++)
- {
- long long a=abs(dot[i].x-dot[j].x)+abs(dot[i].y-dot[j].y);
- if(a%2==1) a++;
- a/=2;
- ti[i][j]=ti[j][i]=a;
- }//计算距离,此处可以画图理解
- for(int o=1;o<=n;o++)
- for(int p=o+1;p<=n;p++)
- {
- long long cntmin=1e12;
- for(int i=1;i<=n;i++)
- for(int j=i+1;j<=n;j++)
- cntmin=min(cntmin,ti[i][j]);,,求最小值
- for(int i=1;i<=n;i++)
- for(int j=i;j<=n;j++)
- if(ti[i][j]==cntmin)
- {
- ti[i][j]=ti[j][i]=1e12;
- map[i][j]=map[j][i]=1;
- }//覆盖,否则min会重复求解
- for(int i=1;i<=n;i++)
- book[i]=0;、、刷新book
- dfs(1);
- int flag=1;
- for(int i=1;i<=n;i++)
- if(book[i]==0)
- flag=0;
- if(flag==1)
- {
- printf("%lld",cntmin);
- return 0;
- }//cntmin即最短时间
- }
- return 0;
- }
复制代码
|