导弹防御塔
C++ 代码
/*
时间较短时能击退所有入侵者,那么对于更长时间,显然也能击退入侵者,因此答案具有单调性,可以二分。
那么对于当前的二分值 mid,就需要判断能否在 mid 秒之内击退所有入侵者。
已知发射预热时间 t1、冷却时间 t2,我们容易计算出每座塔在 mid 分钟内最多能发射出多少枚导弹,记为 p。
可以发现,本题是一个多重匹配问题,可以把入侵者作为二分图的左部节点,每座防御塔拆成 p 个导弹,作为二分图的右部节点。
最终会有 m 个左部节点、n * p 个右部节点
注意,因为塔和入侵者的坐标各不相同,所以从塔飞到入侵者的时间也可能不同,所以在连边时,还需要检查导弹是否有足够的
时间飞到入侵者。因此,一座塔的 p 个导弹是不等价的,这个多重匹配问题必须用拆点来解决。如果 mid 时间内,第 i 个入侵
者能被第 j 座塔的第 k 个导弹击中,那么就在第 i 个左部节点和第 (j - 1) * p + k 个右部节点之间连一条无向边。
然后用匈牙利算法求最大匹配数,若左部节点都能找到匹配,说明 mid 时间内能击退入侵者,二分左区间,否则二分右区间。
*/
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 55;
const double eps = 1e-9;
int n, m;
double t1, t2, v;
PII a[N], b[N]; //入侵者、塔的坐标
double dist[N][N]; //每个入侵者和塔之间的距离
bool st[N * N];
int match[N * N];
vector<int> e[N]; //e[i] 存储所有能打到第i个入侵者的导弹
double get_dist(int i, int j) //计算第i个入侵者和第j座塔之间的距离
{
double x = a[i].first - b[j].first, y = a[i].second - b[j].second;
return sqrt(x * x + y * y);
}
bool find(int u) //匹配
{
for(int i = 0; i < e[u].size(); i++)
{
int j = e[u][i];
if(st[j]) continue;
st[j] = true;
if(!match[j] || find(match[j]))
{
match[j] = u;
return true;
}
}
return false;
}
bool check() //判断能否击退所有入侵者
{
memset(match, 0, sizeof match); //重置匹配数组
for(int i = 1; i <= m; i++) //枚举所有入侵者
{
memset(st, 0, sizeof st); //重置标记数组
if(!find(i)) return false; //只要有一个入侵者无法击退,则返回false
}
return true; //到这说明所有入侵者都能击退,返回true
}
int main()
{
scanf("%d%d%lf%lf%lf", &n, &m, &t1, &t2, &v);
t1 /= 60; //转化成分钟
for(int i = 1; i <= m; i++) scanf("%d%d", &a[i].first, &a[i].second); //入侵者的坐标
for(int i = 1; i <= n; i++) scanf("%d%d", &b[i].first, &b[i].second); //塔的坐标
//计算所有入侵者和塔之间的距离
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
dist[i][j] = get_dist(i, j);
double l = 0, r = 1e9; //二分
while(r - l > eps)
{
double mid = (l + r) / 2;
int p = (mid + t2) / (t1 + t2); //计算在mid时间内每座塔最多能发射多少枚导弹
p = min(p, m); //导弹数量最多只需要m枚
for(int i = 1; i <= m; i++) //枚举每个入侵者
{
e[i].clear(); //清空边
for(int j = 1; j <= n; j++) //枚举所有塔
for(int k = 1; k <= p; k++) //枚举每一发导弹
//如果mid时间内第j座塔的第k发导弹能击退当前入侵者,连一条边
if(k * t1 + (k - 1) * t2 + dist[i][j] / v < mid - eps)
e[i].push_back((j - 1) * p + k); //为了简便,这里用容器来存边
}
if(check()) r = mid; //如果mid时间内能击退所有敌人,尝试缩短时间
else l = mid; //否则需要扩大时间
}
printf("%.6lf\n", r);
return 0;
}
check 里面没必要写 check(mid),直接写 check 就行
已修正~~
妙哉妙哉 写的清晰明了
谢谢hh