链接
https://ac.nowcoder.com/acm/problem/51274
题意
$N$ 座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚
在发射导弹时，导弹需要 $T1$ 秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要 $T2$ 分钟来冷却
所有导弹都有相同的匀速飞行速度 $V$，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离 $Distance$ 时，你只需要计算水平距离，而忽略导弹飞行的高度
导弹在空中飞行的时间就是 $Distance/V$ 分钟，导弹到达目标后可以立即将它击毁
给出 $N$ 座导弹防御塔的坐标，$M$ 个入侵者的坐标，$T1$、$T2$ 和 $V$，你需要求出至少要多少分钟才能击退所有的入侵者
思路
二分答案
将每个防御塔拆成 $m$ 个点，代表该防御塔发射第几个炮弹
如果炮弹打中目标时间小于等于 $mid$，则加边
建完图后跑二分图最大匹配，判断匹配数是否为 $m$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=3000;
int n,m,match[N];
DB t1,t2,v,ax[N],ay[N],bx[N],by[N];
bool st[N];
VI g[N];
bool dfs(int u) {
for(auto v:g[u]) {
if(st[v]) continue;
st[v]=true;
if(match[v]==-1||dfs(match[v])) {
match[u]=v;
match[v]=u;
return true;
}
}
return false;
}
bool check(DB mid) {
for(int i=1;i<=m*(n+1);i++) g[i].clear();
for(int i=1;i<=n;i++)
for(int k=1;k<=m;k++)
for(int j=1;j<=m;j++) {
if(sqrt((ax[i]-bx[j])*(ax[i]-bx[j])+(ay[i]-by[j])*(ay[i]-by[j]))/v+k*t1+(k-1)*t2-mid<1e-8) {
g[i*m+k].PB(j);
g[j].PB(i*m+k);
}
}
for(int i=1;i<=m*(n+1);i++) match[i]=-1;
int res=0;
for(int i=1;i<=m*(n+1);i++) {
if(match[i]!=-1) continue;
for(int j=1;j<=m*(n+1);j++) st[j]=false;
if(dfs(i)) res++;
}
return res==m?true:false;
}
int main() {
scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&v);
t1/=60;
for(int i=1;i<=m;i++) scanf("%lf%lf",&bx[i],&by[i]);
for(int i=1;i<=n;i++) scanf("%lf%lf",&ax[i],&ay[i]);
DB l=0,r=10000000;
while(r-l>1e-8) {
DB mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.6f\n",r);
return 0;
}
|