题目请戳这里

题目大意：一个城市n个点，现在要建m个消防站，消防站建在给定的n个点中。求建m个消防站后，m个消防站要覆盖所有的n个点的覆盖半径最小。

题目分析：重复覆盖问题，DLX解决。不过要求覆盖半径最小，需要二分。虽然给的范围并不大，DLX毕竟还是暴力搜索，而且精度有6位小数，因此直接二分距离的话会TLE！解决方案是将图中任意2点的距离记录下来，去重后二分已知的距离。因为消防站建在给定的n个点中，那么最小覆盖半径一定在任意2点距离中产生。

DLX搜索的时候，一般习惯删除的时候从左往右，不过效率却不一定高。比如这题，从左向右删除和从右向左删除，跑的时间至少差了1s以上！可见用dancing links搜索的时候姿势还是很重要的。有时候换个姿势也许效率更高~

详情请见代码：

#include <iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int N = 51;

const int M = 30001;

const double eps = 1e-7;

double dis[N][N];

double tle[M];

int s[M],h[M],u[M],d[M],l[M],r[M],col[M],row[M];

int point[N][2];

int m,n,num,len;

int fs;

double getdis(int i,int j)

{

    return sqrt((double)(point[i][0] - point[j][0])*(point[i][0] - point[j][0])

               +(double)(point[i][1] - point[j][1])*(point[i][1] - point[j][1]));

}

void read()

{

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

    int i,j;

    len = 1;

    tle[len ++] = 0;

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

    {

        dis[i][i] = 0.0;

        scanf("%d%d",&point[i][0],&point[i][1]);

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

            dis[i][j] = dis[j][i] = getdis(i,j),tle[len ++] = dis[i][j];

    }

}

void init()

{

    memset(h,0,sizeof(h));

    memset(s,0,sizeof(s));

    for(int i = 0;i <= n;i ++)

    {

        u[i] = d[i] = i;

        l[i] = (i + n) % (n + 1);

        r[i] = (i + 1) % (n + 1);

    }

    num = n + 1;

}

void add(int i,int j)

{

    if(h[i])

    {

        r[num] = h[i];

        l[num] = l[h[i]];

        r[l[num]] = l[r[num]] = num;

    }

    else

        h[i] = l[num] = r[num] = num;

    s[j] ++;

    u[num] = u[j];

    d[num] = j;

    d[u[num]] = num;

    u[j] = num;

    col[num] = j;

    row[num] = i;

    num ++;

}

void build(double md)

{

    int i,j;

    init();

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

        for(j = 1;j <= n;j ++)

            if(md - dis[i][j] > -eps)

                add(i,j);

}

void remove(int c)

{

    for(int i = d[c];i != c;i = d[i])

        l[r[i]] = l[i],r[l[i]] = r[i],s[col[i]] --;

}

void resume(int c)

{

    for(int i = u[c];i != c;i = u[i])

        l[r[i]] = r[l[i]] = i,s[col[i]] ++;

}

int A()

{

    int i,j,k,ret = 0;

    bool vis[N];

    memset(vis,false,sizeof(vis));

    for(i = l[0];i;i = l[i])

    {

        if(vis[i] == false)

        {

            vis[i] = true;

            ret ++;

            for(j = d[i];j != i;j = d[j])

                for(k = r[j];k != j;k = r[k])

                    vis[col[k]] = true;

        }

    }

    return ret;

}

void dfs(int k)

{

    if(k + A() >= fs)

        return;

    int i,j;

    if(!r[0])

    {

        fs = min(fs,k);

        return;

    }

    int mn = 1000000;

    int c;

    for(i = l[0];i;i = l[i])

    {

        if(mn > s[i])

        {

            mn = s[i];

            c = i;

        }

    }

    for(i = d[c];i != c;i = d[i])

    {

        remove(i);

        for(j = l[i];j != i;j = l[j])

        {

            remove(j);

        }

        dfs(k + 1);

        for(j = r[i];j != i;j = r[j])

        {

            resume(j);

        }

        resume(i);

    }

}

void solve()

{

    int la,ra,mid,ans;

    sort(tle + 1,tle + len);

    int i = len;

    int j;

    len = 2;

    for(j = 2;j < i;j ++)

        if(fabs(tle[j] - tle[j - 1]) > eps)

            tle[len ++] = tle[j];

    len --;

    la = 1;ra = len;

    while(la <= ra)

    {

        mid = (la + ra)>>1;

        build(tle[mid]);

        fs = M;

        dfs(0);

        if(fs <= m)

        {

            ans = mid;

            ra = mid - 1;

        }

        else

            la = mid + 1;

    }

    printf("%f\n",tle[ans]);

}

int main()

{

    int _;

    scanf("%d",&_);

    while(_ --)

    {

        read();

        solve();

    }

    return 0;

}

//1953MS  636K