「一本通 1.2 练习 2」扩散

发表于 更新于 分类于
  • 题目算法：见 _标签_ （在最下面用’#’和’_’组成）

  • 题目大意：有n个点，每个时间单位会向四周（上下左右）扩散一个点，并且定义一个概念连通块——图内任何两点都联通（即两个点以及扩散出去的点有公共部分），求形成连通块的最短时间。

  • 题目分析：通过求最小值我们很容易就联想到二分。那么连通块如何求？根据定义，我们直接从第1个点开始广搜，搜完能够扩散的点，看看能否到达剩余n-1个点就可以了。用l,r来枚举时间，具体解释见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define gc getchar()
#define Maxn 60
using namespace std;
int sc() { //快读 
	int xx=0,ff=1; char cch;
	while(cch<'0'|| cch>'9') {
		if(cch=='-') ff=-ff; cch=gc;
	}
	while(cch>='0'&& cch<='9') {
		xx=xx*10+(cch-48); cch=gc;
	}
	return xx*ff;
}
struct Map { //建一个结构体来存坐标 
	int x,y;
}a[Maxn];
int n,l,r,ans; //ans为最短时间 
bool pd[Maxn]; //pd[]为从第1个点开始扩散能到达的点(pd[i]=1，即为第1个点和第i个点联通) 
queue <int> q; //广搜标配——队列，存序号 
namespace DY {
	int aabs(int x) { //绝对值函数，因为cmath里的abs()的返回值为double类型，安全起见，自己写int类型 
		return x> 0? x: -x;
	}
	int Manhattan(int u,int v) { //求u,v两点的曼哈顿距离，用来判断从u能否扩散到v 
		return aabs(a[u].x-a[v].x)+aabs(a[u].y-a[v].y);
	}
	bool check(int mid) { //判断时间为mid时，能否形成连通块 
		memset(pd,0,sizeof(pd)); //数组清零 
		q=queue <int> (); //队列清空 
		q.push(1); //从第1个点出发，当然要入队且记录 
		pd[1]=1; 
		while(!q.empty()) { //bfs
			int now=q.front(); q.pop();
			for(int i=1; i<=n; i++) { //枚举每一个点 
				if(pd[i]|| Manhattan(now,i)> 2*mid) continue; //如果这个点被访问过或两个点的曼哈顿距离超过两倍的时间，前者是不用再处理了，后者是不能扩散到。 
				//为什么曼哈顿距离小于2倍时间到达不了呢？
				/*当时间为mid时，第now个点最多扩散mid个距离，第i个点最多也是扩散mid个距离，
				当曼哈顿距离比最大扩散距离还大，当然是不能扩散到。*/ 
				pd[i]=1; //记录+入队 
				q.push(i);
			}
		}
		for(int i=1; i<=n; i++) //判断是否到达每一个点 
			if(!pd[i]) return 0; //有 没有到达的点，跳出 
		return 1; //形成连通块 
	}
	void main() {
		n=sc(); //输入 
		for(int i=1; i<=n; i++) {
			a[i].x=sc(); a[i].y=sc();
			r=max(r,max(a[i].x,a[i].y));
		}
		while(l<=r) { //二分模板 
			int mid=l+r>>1;
			if(check(mid)) r=mid-1,ans=mid; //如果能形成连通块，时间越小越好，所以要缩小r 
			else l=mid+1; //形成不了连通块，说明时间不够，所以要扩大l 
		}
		printf("%d",ans); //输出 
	}
};
int main() {
	DY::main();
	return 0;
}

祝各位OIer( _Of course including me_ )

RP++;