题解 | 算法进阶指南 导弹防御塔

我们考虑跑 网络流 首先是 二分图最大匹配 == 入侵者数量时 时间可以缩小
点才最多50个 50 * 50 最多发 3000 不到的导弹
3000 和 原点连 3000个边
3000 和 入侵者连 最多15000边
开 前向星 按 40000 * 8 边 差不多了就 因为连的太多了
暴力点建图 将塔分成很多导弹
每个点 最多建立50个 我们预先建出来 原点到炮塔发出得导弹上
之后 按炮弹发射和冷却路上总时间 和 入侵者相连
最后 入侵者与汇点相连
我们跑最大流 如果 最大流不是 入侵者数目 r = mid 不然 l = mid

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 40000;

int n, m;
double t1, t2, v;
int s, t;
int head[10000], depth[10000], cur[10000], cnt;
int nxt[maxn << 3], to[maxn << 3], cap[maxn << 3];  

void ade(int a, int b, int c) {
    to[cnt] = b;
    cap[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt ++;
}

bool bfs(){
    queue<int> que;
    que.push(s);
    memset(depth, 0, sizeof(depth));
    depth[s] = 1;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; i != -1; i = nxt[i]) {
            if(cap[i] > 0 && depth[to[i]] == 0) {
                depth[to[i]] = depth[u] + 1;
                que.push(to[i]);
            }
        }
    }
    if(depth[t]) return 1;
    else return 0;
}

int dfs(int u, int dist) {
    if(u == t) return dist;
    for(int &i = cur[u]; i != -1; i = nxt[i]) {
        if(depth[to[i]] == depth[u] + 1 && cap[i] > 0) {
            int tmp = dfs(to[i], min(dist, cap[i]));
            if(tmp > 0) {
                cap[i] -= tmp;
                cap[i ^ 1] += tmp;
                return tmp; 
            }
        }
    }
    return 0;
}

struct node{
    int x, y;
}army[55], tower[55];

int dinic() {
    int res = 0, d;
    while(bfs()) {
        for(int i = 0; i < 10000; i ++) cur[i] = head[i];
        while(d = dfs(s, INF)) res += d;
    }
    return res;
}

double getdis(node a, node b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void init(double time){
    memset(head, -1, sizeof(head));
    cnt = 0;
    for(int i = 1; i <= n; i ++) for(int j = 0; j <= m; j ++) 
            ade(s, i + j * 55, 1), ade(i + j * 55, s, 0);
    for(int i = 1; i <= n; i ++) {
        double sec;
        for(int j = 0; j < m; j ++) {
            sec = (1.0 * t1 + 1.0 * j * (t1 + t2));
            for(int k = 1; k <= m; k ++) {
                if(sec + getdis(army[k], tower[i]) / v < time)
                    ade(i + j * 55, 4000 + k, 1), ade(4000 + k, i + j * 55, 0);
            }
        }
    }
    for(int i = 1; i <= m; i ++)
        ade(4000 + i, t, 1), ade(t, 4000 + i, 0);
}

int main(){
    cin >> n >> m >> t1 >> t2 >> v;
    t1 /= 60;
    s = 0, t = 9000;
    for(int i = 1; i <= m; i ++) cin >> army[i].x >> army[i].y;
    for(int i = 1; i <= n; i ++) cin >> tower[i].x >> tower[i].y;
    double l = 0, r = 200000;
    while((r - l) > 1e-7) {
        double mid = (l + r) / 2;
        init(mid);
        if(dinic() == m) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", r);
    return 0;
}