CH6803 导弹防御塔（二分图匹配）

痛定思痛。 2021-11-09 23:04 168阅读 0赞

## 题意：Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。现在，给出N座导弹防御塔的坐标，M个入侵者的坐标，T1、T2和V，你需要求出至少要多少分钟才能击退所有的入侵者。 ##

## 分析：抽象成导弹与入侵者的匹配问题，详见《算法竞赛进阶指南》P423。 ##

## 代码： ##

#include <cmath>
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <iostream>
    #define pii pair<int, int>
    #define x first
    #define y second
    using namespace std;
    const int N = 56, M = 2506;
    const double eps = 1e-8;
    int n, m, t, t2, V, f[M];
    double t1;
    bool v[M];
    pii a[N], b[N];
    pair<int, double> c[M];
    vector<int> e[N];
    
    inline double S(pii a, pii b) {
    	int dx = a.x - b.x, dy = a.y - b.y;
    	return sqrt(dx * dx + dy * dy);
    }
    
    bool dfs(int x) {
    	for (unsigned int i = 0; i < e[x].size(); i++) {
    		int y = e[x][i];
    		if (v[y]) continue;
    		v[y] = 1;
    		if (!f[y] || dfs(f[y])) {
    			f[y] = x;
    			return 1;
    		}
    	}
    	return 0;
    }
    
    inline bool pd(double mid) {
    	memset(f, 0, sizeof(f));
    	for (int i = 1; i <= m; i++) {
    		e[i].clear();
    		for (int j = 1; j <= t; j++)
    			if (c[j].y + S(a[i], b[c[j].x]) / V <= mid)
    				e[i].push_back(j);
    	}
    	for (int i = 1; i <= m; i++) {
    		memset(v, 0, sizeof(v));
    		if (!dfs(i)) return 0;
    	}
    	return 1;
    }
    
    int main() {
    	cin >> n >> m >> t1 >> t2 >> V;
    	t = n * m;
    	t1 /= 60;
    	for (int i = 1; i <= m; i++)
    		scanf("%d %d", &a[i].x, &a[i].y);
    	for (int i = 1; i <= n; i++)
    		scanf("%d %d", &b[i].x, &b[i].y);
    	for (int i = 1; i <= m; i++)
    		for (int j = 1; j <= n; j++) {
    			int k = (i - 1) * n + j;
    			c[k].x = j;
    			c[k].y = (i - 1) * (t1 + t2) + t1;
    		}
    	double l = t1, r = 100000;
    	while (l + eps < r) {
    		double mid = (l + r) / 2;
    		if (pd(mid)) r = mid;
    		else l = mid;
    	}
    	printf("%.6f\n", l);
    	return 0;
    }