暑假集训前难题复习

扩散

洛谷P1661

分析

二分(寻找最小的时间)+并查集(检验是否构成连通块)

AC代码

#include <cstdio>
#include <cmath>
#include <cstring>

#define LL long long

using namespace std;

const int MAXN = 55;

struct node {
	LL x;
	LL y;
} nodes[MAXN];

int n, dict[MAXN];
LL left = 0, right = 1e9;//二分的极值

LL distance (node a, node b) { return abs(a.x - b.x) + abs(a.y - b.y); }//返回两个点的曼哈顿距离

int zuisu (int x) {
	if (dict[x] == x) return x;
	return zuisu(dict[x]);
}

bool check (LL x) {
	memset(dict, 0, sizeof(dict));//每次检查都将上一次的标记重置
	for (int i = 1; i <= n; i++) {
		dict[i] = i;//并查集初始化
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (distance(nodes[i], nodes[j]) <= x * 2) {
			//因为扩散是四个方向都有,所以要求两个点的曼哈顿距离的二分之一小于x,为了保持精度,这里为小于二倍x
				LL xx = zuisu(i);
				LL yy = zuisu(j);
				dict[xx] = yy;//并查集找祖宗
			}
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (dict[i] == i) sum++;//统计祖宗数,即查看共有多少个连通块
	return (sum == 1);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld%lld", &nodes[i].x, &nodes[i].y);
	}
	int ans;
	while (right >= left) {//二分
		LL mid = (right + left) >> 1;
		if (check(mid)) {
			right = mid - 1;
			ans = mid;
		}
		else left = mid + 1;
	}
	printf("%lld", ans);
	return 0;
}