洛谷P1783海滩防御

题目

跟奶酪那道题差不多，用并查集来求解。

用二分，或可以用类似于克鲁斯卡尔算法的贪心来每次判断是否起点和终点已经并在一个集合里(类似奶酪)

如果已经覆盖就结束判断并得出答案：即当前选择的边的最大值。

为什么是边的最大值呢。

我们考虑最小的工作半径一定是等于两点间的一个距离，如果大于一个两点间的距离而又小于一个两点间的距离时，则可以选择小的两点间的距离从而使答案更小。所以可以枚举所有的两点间的距离然后判断到哪一个距离可使海滩封锁。

#include <bits/stdc++.h>
#define N 1010000
#define M 1011
using namespace std;
int n, m, cnt, x[N], y[N], fa[N];
double ans, dis[M][M];
struct stree {
    int x, y;   
    double dis;
}e[N];
bool cmp(stree a, stree b) {
    return a.dis < b.dis;
}   
double dist(int x1, int x2, int y1, int y2) {
    return sqrt( (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) );
}        
int find(int a)
{        
    if (fa[a] == a) return a;
    return fa[a] = find(fa[a]);
}
inline void krus()
{   
    int i;
    for (i = 0; i <= cnt; i++)
    {
        
        int f1 = find(e[i].x), f2 = find(e[i].y);
        if (f1 != f2)   
            fa[f2] = f1;
        if (find(0) == find(m + 1)) break;
    }
    printf("%.2lf", e[i].dis);
    exit(0);
}           
int main()
{       
//  memset(fa, -1, sizeof(fa)); 
    scanf("%d%d", &n, &m); if (m == 0) printf("0"), exit(0);
    for (int i = 0; i <= m + 1; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) scanf("%d%d", &x[i], &y[i]);//m + 1是虚点 
    for (int i = 1; i < m; i++)
        for(int j = i + 1; j <= m; j++)
        {
            e[++cnt].x = i;
            e[cnt].y = j;
            e[cnt].dis = dist ( x[i], x[j], y[i], y[j] ) / 2.0000;
        }
    for (int i = 1; i <= m; i++)
    {   
        e[++cnt].x = i, e[cnt].y = 0,     e[cnt].dis = x[i];
        e[++cnt].x = i, e[cnt].y = m + 1, e[cnt].dis = n - x[i];
    }
    sort(e + 1, e + 1 + cnt, cmp); 
    krus();
}   

洛谷P1783海滩防御

原文：https://www.cnblogs.com/liuwenyao/p/11002548.html