HDU 3585 maximum shortest distance

淦啊……我之前自以为入门的最大团DP优化板子是错的，我说怎么和极大团计数差别这么多，那个原先的根本就是一个被谁自创的dfs+dp优化算法，速度平均慢一倍！！！

说句别的，终于刷完这套……给出链接
最大团与稳定婚姻专题

题意：
要你找出一个数量不小于 k 的最大团，使得最大团中的最短距离最大。

思路：
二分距离+最大团判定

老实说我一开始没想到，但看到这个思路之后就是豁然开朗，感觉二分的思路都是这样的……
然后疯狂TLE……不知道为什么，查了一下，最大团板子太慢了……原来学得是民间算法！！

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset(ary, (num), sizeof(ary))

using namespace std;

typedef pair<int, int> pii;
const int maxn = 55;

int n, k, ans;
pii point[maxn];
int some[maxn][maxn], dis[maxn][maxn];
int len[maxn * maxn], alimit;

inline int two(int x) { return x * x; }

int calc(int a, int b)
{
    return two(point[a].first - point[b].first) + two(point[a].second - point[b].second);
}

bool dfs(int deep, int sn, int an)
{
    if (an >= k)
        return true;
    if (sn + an < k)
        return false;
    int u = some[deep][1];
    range(i, 1, sn)
    {
        int v = some[deep][i];
        if (dis[u][v] >= alimit)
            continue;
        int tsn = 0;
        range(j, 1, sn) if (dis[v][some[deep][j]] >= alimit) some[deep + 1][++tsn] = some[deep][j];
        if (dfs(deep + 1, tsn, an + 1))
            return true;
        some[deep][i] = 0;
    }
    return false;
}

bool check(double limit)
{
    range(i, 1, n) some[1][i] = i;
    alimit = limit;
    return dfs(1, n, 0);
}

int main()
{
    while (scanf("%d %d", &n, &k) != EOF) {
        range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
        int num = 0;
        range(i, 1, n) range(j, i + 1, n)
        {
            dis[i][j] = dis[j][i] = calc(i, j);
            len[num++] = dis[i][j];
        }
        sort(len, len + num);
        int l = 0, r = num - 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (check(len[mid]))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%.2f\n", sqrt(len[l - 1]));
    }
    return 0;
}