题解：P10936 导弹防御塔

为什么是二分图？

注意到一个小怪会被一个导弹秒了，但是一个防御塔是可以输出多枚导弹的，这个时候一一对应的关系被隐藏了，本质上其实是导弹和小怪的二分图，而攻击问题就转化成了匹配问题。

怎么描述问题？

注意到一次导弹攻击可以用如下的方法唯一确定：导弹 在 时刻开始从防御塔起飞，打向 小怪。由于我们知道 ，是可以计算出消灭这个小怪的结束时间的。

所以点的描述就很清晰了，一边是导弹，另一边是小怪，维护以上信息：下标、起飞时间。

为什么二分答案？

但是又注意到另一个问题：权值。简单的最大匹配只能处理个数而不能处理权值，这就涉及最优解问题转可行性问题，这正是二分答案的重要作用。

怎么建图？

因为目标是检测可行性，说明在时间限制 以内的边是可以连的，否则不可以。

则思路就是：对于防御塔 ，枚举第 发导弹，攻击小怪 ，计算这个过程的时间，如果在 以内，就连边。（这里邻接表会方便一点，下文实现采取这个方式）

好的，在现在这个图上跑最大匹配，看看是否能够连 条边，毕竟一个边秒一个小怪。

注意单位。

#include<bits/stdc++.h>
#define dwb double

using namespace std;

const int MAXN = 55;
const dwb eps = 1e-7;

dwb n, m, t1, t2, v;
dwb tx[MAXN], ty[MAXN];
dwb mx[MAXN], my[MAXN];

int nodeCnt;
vector<int> edge[MAXN * MAXN];

int match[MAXN];
bool vis[MAXN];

inline dwb calDist(dwb x1_, dwb y1_, dwb x2_, dwb y2_) {
    return sqrt((x1_ - x2_) * (x1_ - x2_) + (y1_ - y2_) * (y1_ - y2_));
}

inline void reset() {
    nodeCnt = 0;
    for (int i = 1; i <= n * m; ++i)
        edge[i].clear();
    memset(match, 0, sizeof(match));
    return;
}
inline void build(dwb TLE) {
    for (int i = 1; i <= n; ++i)
        for (int k = 0; k < m; ++k) {
            dwb fireTime = t1 + (dwb)k * (t1 + t2);
            if (fireTime > TLE)
                break;
            nodeCnt++;
            for (int j = 1; j <= m; ++j) {
                dwb flyTime = calDist(tx[i], ty[i], mx[j], my[j]) / v;
                if (fireTime + flyTime <= TLE)
                    edge[nodeCnt].push_back(j);
            }
        }
    return;
}
inline bool dfs(int from) {
    for (int to : edge[from]) {
        if (vis[to])	continue;
        vis[to] = true;
        if (!match[to] || dfs(match[to])) {
            match[to] = from;
            return true;
        }
    }
    return false;
}
inline bool check(dwb TLE) {
    reset();
    build(TLE);
    int res = 0;
    for (int from = 1; from <= nodeCnt; ++from) {
        memset(vis, 0, sizeof(vis));
        if (dfs(from))
            res++;
    }
    return res == m;
}

int main() {
    scanf("%lf%lf%lf%lf%lf", &n, &m, &t1, &t2, &v);
    t1 /= 60.0;
    for (int i = 1; i <= m; ++i)
        scanf("%lf%lf", &mx[i], &my[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &tx[i], &ty[i]);
    dwb l = 0, r = 1e6;
    while (r - l > eps) {
        dwb mid = l + (r - l) / 2;
        check(mid) ? r = mid : l = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}