啊哈磊_编程从这里起步
标题:
本来要发题解的,然后卡住发不了的题解。。。12144扩散 搜索题解
[打印本页]
作者:
XZG
时间:
2018-10-2 16:18
标题:
本来要发题解的,然后卡住发不了的题解。。。12144扩散 搜索题解
先看题。。。此题数据比较水(毕竟只有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;
}
复制代码
作者:
班德尔城小呆猫
时间:
2018-10-2 16:20
收到了
大佬 orz
作者:
XZG
时间:
2018-10-2 16:21
班德尔城小呆猫 发表于 2018-10-2 16:20
收到了
大佬 orz
%%%%%%%%%%%%%%%%%%%
欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)
Powered by Discuz! X3.2