导弹防御塔

AcWing-374-导弹防御塔

分析

见《进阶指南》第428页。

实现

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 52, M = 2510;
const double eps = 1e-8;
struct edge {
    int to, next;
};
edge e[2 * N * M];
int idx, head[N + M];
struct node {
    int x;
    double y;
};
int n, m, t2, v;
double t1;
node a[N], b[N], c[M];
int ln, rn;
bool mark[N + M];
int match[N + M];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
double dis (const node& a, const node& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
bool dfs (int cur) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (mark[to] == true) continue;
        mark[to] = true;
        if (match[to] == 0 || dfs(match[to]) == true) {
            match[to] = cur;
            return true;
        }
    }
    return false;
}
bool check (double x) {
    idx = 0;
    memset(head, -1, sizeof(head));
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= ln; ++ i) {
        for (int j = 1; j <= rn; ++ j) {
            if (c[j].y + dis(a[i], b[c[j].x]) / v <= x) {
                add_edge(i, ln + j);
                add_edge(ln + j, i);
            }
        }
    }
    for (int i = 1; i <= ln; ++ i) {
        memset(mark, 0, sizeof(mark));
        if (dfs(i) == false) return false;
    }
    return true;
}

int main () {
    cin >> n >> m >> t1 >> t2 >> v;
    for (int i = 1; i <= m; ++ i) // 入侵者
        cin >> a[i].x >> a[i].y;
    for (int i = 1; i <= n; ++ i) // 防御塔
        cin >> b[i].x >> b[i].y;
    
    t1 = t1 / 60; // 秒 -> 分
    ln = m;
    for (int i = 1; i <= n; ++ i) // 防御塔
        for (int j = 1; j <= m; ++ j) // 入侵者
            c[++ rn] = { i, (j - 1) * (t1 + t2) + t1 }; // 拆点
    
    double l = t1, r = 200000;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid) == true)
            r = mid;
        else
            l = mid;
    }
    printf("%.6lf", l);
    return 0;
}