描述 Description
Freda 的城堡——
“Freda，城堡外发现了一些入侵者！”
“喵… 刚刚探究完了城堡建设的方案数，我要歇一会儿嘛 lala~”
“可是入侵者已经接近城堡了呀！”
“别担心，rainbow，你看呢，这是我刚设计的导弹防御系统的说~”
“喂… 别卖萌啊……”
Freda 控制着 N 座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要 T1 秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要 T2 分钟来冷却。
所有导弹都有相同的匀速飞行速度 V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离 Distance 时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。
现在，给出 N 座导弹防御塔的坐标，M 个入侵者的坐标，T1、T2 和 V，你需要求出至少要多少分钟才能击退所有的入侵者。
求在装置互不攻击的情况下，最多可以放置多少个装置。
输入格式 InputFormat
第一行五个正整数 N,M,T1,T2,V。
接下来 M 行每行两个整数，代表入侵者的坐标。
接下来 N 行每行两个整数，代表防御塔的坐标。
输出格式 OutputFormat
输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。
样例输入 SampleInput
6 6 42 468 335
9169 6500
1478 5724
6962 9358
5705 4464
3281 8145
9961 6827
2995 491
4827 1942
2391 5436
3902 4604
292 153
7421 2382
样例输出 SampleOutput
19.491354
二分时间，将每个防御塔拆成 m 个点，表示第几次发射导弹，预处理每个防御塔到入侵者的距离，每次二分之后根据时间建二分图，匈牙利算法判断二分图最大匹配是否覆盖所有入侵者。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define sqr(s) (s)*(s)
const int maxn=55*55*55;
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,k,z,y,x;
struct edge
{
int to,nx;
}e[maxn];
int head[maxn],match[maxn];
bool used[maxn];
pair <int,int> a[maxn],b[maxn];
int cnt,mat,v;
double tim[55][55],c[maxn];
double l,r,mid,t1,t2;
inline void ins(int u,int v)
{
e[++cnt].to=v;e[cnt].nx=head[u];
head[u]=cnt;
}
bool crosspath(int s)
{
int i,j,t,u,v,w;
for (i=head[s];i;i=e[i].nx)
{
v=e[i].to;
if (!used[v])
{
used[v]=true;
if (!match[v] || crosspath(match[v]))
{
match[v]=s;
return true;
}
}
}
return false;
}
inline bool hungary(int s)
{
int i,j,t;
for (i=1;i<=s;i++)
{
memset(used,false,sizeof(used));
if (!crosspath(i)) return false;
}
return true;
}
inline bool can(double s)
{
int i,j,t,k;
mat=cnt=0;
memset(head,0,sizeof(head));
memset(match,0,sizeof(match));
for (i=1;i<=m;i++) for (j=1;j<=n;j++) for (k=1;k<=m;k++)
{
if (c[k]+tim[i][j]<=s) ins(i,j*m+k);
else break;
}
return hungary(m);
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&x,&y,&v);
t1=(double)x/60;t2=y;
for (i=1;i<=m;i++) scanf("%d%d",&a[i].first,&a[i].second);
for (i=1;i<=n;i++) scanf("%d%d",&b[i].first,&b[i].second);
for (i=1;i<=m;i++) for (j=1;j<=n;j++) tim[i][j]=((double)sqrt(((double)(a[i].first-b[j].first)*(a[i].first-b[j].first)+(a[i].second-b[j].second)*(a[i].second-b[j].second))))/v;
for (i=1;i<=m;i++) c[i]=t1*i+t2*(i-1);
l=0;r=inf;
while (r-l>1e-7)
{
mid=(l+r)/2;
if (can(mid)) r=mid;
else l=mid;
}
printf("%.6lf\n",l);
return 0;
}