题面
Freda的城堡遭受了 M 个入侵者的攻击！
Freda控制着 N 座导弹防御塔，每座塔都有足够数量的导弹，但是每次只能发射一枚。
在发射导弹时，导弹需要 T1 秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要 T2 分钟来冷却。
所有导弹都有相同的匀速飞行速度 V，并且会沿着距离最短的路径去打击目标。
计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。
导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。
现在，给出 N 座导弹防御塔的坐标，M 个入侵者的坐标，T1,T2 和 V。因为Freda的小伙伴Rainbow就要来拜访城堡了，你需要求出至少多少分钟才能击退所有的入侵者。
输入格式
第一行五个正整数N,M,T1,T2,V。
接下来 M 行每行两个整数，代表入侵者的坐标。
接下来 N 行每行两个整数，代表防御塔的坐标。
输出格式
输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。
数据范围
1≤N,M≤50,坐标绝对值不超过10000，T1,T2,V不超过2000。
输入样例：
3 3 30 20 1
0 0
0 50
50 0
50 50
0 1000
1000 0
输出样例：
91.500000
题解
多重匹配有四种解决方案
1.把点全部拆开
2,左边点集只能连一次, 那就在匈牙利算法的时候, 依次去匹配 右点 第 k 次连接, 都匹配满, 再去依次重匹配 右点 的 k次连接
3.右点集只能连一次, 可以交换成2, 或者在匈牙利算法的时候让 左点 匹配 k次
4.网络流添加源点和汇点, 直接做
这题我们使用3的减缓做法, 让敌人去匹配子弹
这道题是单调的, 二分时间
判断在此时间内 每个炮塔能发射多少子弹(最多50, 多了没用, 敌人就50个)
敌人和能打到他的子弹连边, 匈牙利就完事
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
const int N = 50 + 5;
int n, m, _, k;
int match[N * N], c;
db t1, t2, sp;
PII a[N], b[N];
bool v[N * N];
double dis(int x, int y) {
return sqr(a[x].fi - b[y].fi) + sqr(a[x].se - b[y].se);
}
bool dfs(int x, double mid) {
per (i, n * c, 1) {
if (dis(x, (i - 1) / c + 1) > sqr(sp) * sqr(mid - (i - 1) % c * (t1 + t2) - t1)) continue;
if (v[i]) continue;
v[i] = 1;
if (!match[i] || dfs(match[i], mid)) { match[i] = x; return 1; }
}
return 0;
}
bool check(double mid) {
c = (int)min((mid + t2) / (t1 + t2), 50.0);
per (i, n * c, 1) match[i] = 0;
rep (i, 1, m) {
per (j, n * c, 1) v[j] = 0;
if (!dfs(i, mid)) return 0;
}
return 1;
}
int main() {
IOS; cin >> n >> m >> t1 >> t2 >> sp; t1 /= 60;
rep (i, 1, m) cin >> a[i].fi >> a[i].se;
rep (i, 1, n) cin >> b[i].fi >> b[i].se;
double l = 0, r = 2e18;
while (r - l >= 1e-8) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
cout << setiosflags(ios::fixed) << setprecision(6) << r;
return 0;
}