[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 }p[N]; inline double D(int i, int j) inline bool cmp(node x, node y) inline int find(int x) int main() std::sort(p + 1, p + cnt + 1, cmp); for(i = 0; i <= m + 1; i++) f[i] = i; for(i = 1; i <= cnt; i++) } }

　　

上一篇：[luoguP2461] [SDOI2008]递归数列（DP + 矩阵优化）

下一篇：[BZOJ2342] [Shoi2011]双倍回文（manacher）

---

二分 最短路 并查集 dijkstra 最小生成树 kruskal