[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）

因为答案满足单调性，所以看到这个题，第一反应是二分，但是总是WA，也没有超时。

看了题解，，，，，，

这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样写明显超时，对于任何一个点，要找到离它最近的信号塔需要O(n)的时间，再乘上M*L（L=海滩的长度）不超时才怪呢。

这一题的本质就是封锁海滩，即用信号塔的工作范围将两边的边界连在一起。所以，这题就是求一条从第0列到第n列的最短路径，用点与边界的距离作为权值，点与点之间的距离的二分之一作为权值，构图完成后，用Dijkstra算法求最短路就可以了。当然用Kruskal算法并查集结构依次加最小边，直到两条边界被连在一起也是可以的。但是要注意最短路的长度是路径上边权的最大值，而不是边权之和

#include <cmath>

#include <cstdio>

#include <algorithm>

#define N 1000001

int f[N];

int n, m, cnt;

double X[N], Y[N];

struct node

{

	int x, y;

	double z;

	node(int x = 0, int y = 0, double z = 0) : x(x), y(y), z(z) {}

}p[N];

inline double D(int i, int j)

{

	return sqrt((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]));

}

inline bool cmp(node x, node y)

{

	return x.z < y.z;

}

inline int find(int x)

{

	return x == f[x] ? x : f[x] = find(f[x]);

}

int main()

{

	int i, j, x, y;

	scanf("%d %d", &n, &m);

	for(i = 1; i <= m; i++) scanf("%lf %lf", &X[i], &Y[i]);

	for(i = 1; i <= m; i++)

		for(j = i + 1; j <= m; j++)

			p[++cnt] = node(i, j, D(i, j) / 2);

	for(i = 1; i <= m; i++)

	{

		p[++cnt] = node(0, i, X[i]);

		p[++cnt] = node(i, m + 1, n - X[i]);

	}

	std::sort(p + 1, p + cnt + 1, cmp);

	for(i = 0; i <= m + 1; i++) f[i] = i;

	for(i = 1; i <= cnt; i++)

	{

		x = find(p[i].x);

		y = find(p[i].y);

		f[x] = y;

		if(find(0) == find(m + 1))

		{

			printf("%.2lf\n", p[i].z);

			return 0;

		}

	}

}

巴特西

[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）

最新文章

热门文章