我们考虑跑 网络流 首先是 二分图最大匹配 == 入侵者数量时 时间可以缩小
点才最多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; }