「AcWing 374」「BZOJ 3035」导弹防御塔

Description

Freda 的城堡遭受了 (M) 个入侵者的攻击！

Freda 控制着 (N) 座导弹防御塔，每座塔都有足够数量的导弹，但是每次只能发射一枚。

在发射导弹时，导弹需要 (T_1) 秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要 (T_2) 分钟来冷却。

所有导弹都有相同的匀速飞行速度 (V)，并且会沿着距离最短的路径去打击目标。

计算防御塔到目标的距离 ( ext{Distance}) 时，你只需要计算水平距离，而忽略导弹飞行的高度。

导弹在空中飞行的时间就是 (( ext{Distance}/V)) 分钟，导弹到达目标后可以立即将它击毁。

现在，给出 (N) 座导弹防御塔的坐标，(M) 个入侵者的坐标，(T_1,T_2) 和 (V)。因为 Freda 的小伙伴 Rainbow 就要来拜访城堡了，你需要求出至少多少分钟才能击退所有的入侵者。

Hint

• (1le N, Mle 50)；
• (1le T_1, T_2, V le 2 imes 10^3)；
• 坐标绝对值不超过 (10^4)。

Solution

直接做不太好做，不如将问题转化一下，判断能否在时间 (t) 内击退所有入侵者。

显然如果在 (t) 时间内可以击退，那么 (t + k(k>0)) 的时间内也一定可以。满足单调性，就可以 二分答案 了。

---

考虑如果一个导弹防御塔如果只能发射一枚导弹，那就是一个 二分图最大匹配 问题。两边的点分别为防御塔和入侵者。

如果可以发射不止一个，那就是 多重匹配问题。

---

多重匹配问题的常规解决方式之一是 拆点。

具体地，就是 (t) 时间内，若该防御塔可以发射 (x) 个导弹，那么就拆成 (x) 个点，然后使每一个入侵者的点向这些点连一条边。

---

对于二分中某一个 (t) 的可行性的判断，只要检查 (m) 个入侵者的点是否都有导弹的点与之匹配即可。

也可以判断最大匹配对数是否等于 (m)。

---

考虑到导弹拆点后点数多且不好控制，推荐从入侵者的点这一边搜。

既减少了代码难度，也大大提高了代码运行效率（(3266 ext{ms} ightarrow 204 ext{ms})）。

匈牙利算法，时间复杂度：(O(n^2m log t))

Code

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : AcWing 374 BZOJ 3035 导弹防御塔
 */
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
const int N = 55;
const int S = 1e4 + 5;
const double eps = 1e-8;

int mis[2][N], inv[2][N];
int n, m, total;
double t1, t2, v;

double cost[N][N];
pair<int, double> extra[S];
#define sqr(x) ((x) * 1.0 * (x))
inline double dist(int x1, int y1, int x2, int y2) {
	return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}

vector<int> G[N];
int match[S], vis[S];

void resetData() {
	for (register int i = 1; i <= m; i++)
		G[i].clear();
	memset(match, 0, sizeof match);
	memset(vis, 0, sizeof vis);
}

bool Dfs(int x, int t) {
	if (vis[x] == t) return false;
	vis[x] = t;
	for (vector<int>::iterator y = G[x].begin(); y != G[x].end(); y++)
		if(!match[*y] || Dfs(match[*y], t))
			return match[*y] = x, true;
	return false;
}

bool judge(double t) {
	resetData();
	for (register int i = 1; i <= m; i++)
		for (register int j = 1; j <= total; j++)
			if (extra[j].second + cost[extra[j].first][i] <= t)
				G[i].push_back(j);
	
	for (register int i = 1; i <= m; i++)
		if (!Dfs(i, i)) return false;
	return true;
}

void calcCost() {
	for (register int i = 1; i <= n; i++)
		for (register int j = 1; j <= m; j++)
			cost[i][j] = dist(mis[0][i], mis[1][i], inv[0][j], inv[1][j]) / v;
	
	total = n * m;
	for (register int i = 1; i <= n; i++)
		for (register int j = 1; j <= m; j++) {
			int pos = (i - 1) * m + j;
			extra[pos] = make_pair(i, t1 + (t1 + t2) * (j - 1));
		}
}

signed main() {
	scanf("%d%d%lf%lf%lf", &n, &m, &t1, &t2, &v);
	t1 /= 60;
	for (register int i = 1; i <= m; i++)
		scanf("%d%d", &inv[0][i], &inv[1][i]);
	for (register int i = 1; i <= n; i++)
		scanf("%d%d", &mis[0][i], &mis[1][i]);
	
	calcCost();
	
	double lb = t1, ub = 1e6;
	while (ub - lb > eps) {
		double mid = (lb + ub) / 2;
		if (judge(mid)) ub = mid;
		else lb = mid;
	}
	printf("%.6f
", ub);
	return 0;
}