[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] 海滩防御（二分 || 最短路 || 最小生成树）

推荐阅读