| 题目名称 | 512. 扩散 |
|---|---|
| 输入输出 | ppg.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2010-11-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：50， 提交：129， 通过率：38.76% | ||||
 +1s |
100 | 0.000 s | 0.00 MiB | C++ |
 xxcxcxcx |
100 | 0.000 s | 0.00 MiB | C++ |
 LGLJ |
100 | 0.000 s | 0.00 MiB | C++ |
 王者自由 |
100 | 0.002 s | 0.17 MiB | Pascal |
 0-0 |
100 | 0.002 s | 0.17 MiB | Pascal |
 苏轼 |
100 | 0.002 s | 0.17 MiB | Pascal |
 liu_runda |
100 | 0.002 s | 0.30 MiB | C++ |
 ty_c7x1 |
100 | 0.002 s | 0.33 MiB | C++ |
 yushi |
100 | 0.003 s | 0.26 MiB | C++ |
 zjmfrank2012 |
100 | 0.003 s | 0.28 MiB | C++ |
| 本题关联比赛 | |||
| 20101118 | |||
| 关于 扩散 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题的prim不加堆优化貌似会快一点
| ||||
|
弱菜使用并查集写的...Max表示当前时间,对于每两个点都更新Max值
即 Max=max(Max,Max+distance[i][j]/2+distance[i][j] Mod 2-Max) 注意distance[i][j]/2+distance[i][j]Mod2表示的是两点到最近公共点的曼哈顿距离.减去Max表示减去已经扩散的距离. 看上去挺麻烦其实就是维护不断增加Max的值直到并查集只剩下一个集合为止(所有的元素都成了一个连通块) 注意distance的值存放在一个一维的不下降数组里,否则就会有答案变大的情况  QhelDIV
2012-06-19 18:24
3楼
| ||||
|
自主构图+最小生成树，
因为用邻接矩阵存的图（似乎用邻接表构图会很麻烦……）， 再加上图是一个不折不扣的稠密图（本来就是完全图）， 用的普里姆算法。（克鲁斯卡尔算法适用于稀疏图，用邻接表的图）。 这里普里姆是用的“不完全”队列操作实现的，感觉应该是普里姆算法中最简单最快的实现方法了。 | ||||
|
找题解，上http://paulinsider.at.ua/news/ppg/2011-11-08-8，快，稳，准，大牛的选择！！
用prim | ||||
Truth.Cirno
苏轼
【问题描述】
在平面上有n个点，一个点每过一个单位时间就会向4个方向（上下左右）扩散一个距离，如下图所示：
两个点a和b连通，记作e(a,b)，当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),……e(ak,v)。给定平面上n个点的坐标，问最早什么时刻它们形成一个连通块。
【输入文件】
第一行一个数：n
下面n行，每行两个整数x,y，代表一个点的坐标。
【输出文件】
一个整数，表示最早的时刻所有点形成的连通块。
【样例输入】
2
0 0
5 5
【样例输出】
5
【数据规模】
对于20%的数据，满足1<=n<=5; 1<=x[i],y[i]<=50;
对于100%的数据，满足1<=n<=50;1<=x[i],y[i]<=10^9