题目
Freda的城堡——
“Freda，城堡外发现了一些入侵者！”
“喵...刚刚探究完了城堡建设的方案数，我要歇一会儿嘛lala~”
“可是入侵者已经接近城堡了呀！”
“别担心，rainbow，你看呢，这是我刚设计的导弹防御系统的说~”
“喂...别卖萌啊……”
Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。
所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。
现在，给出N座导弹防御塔的坐标，M个入侵者的坐标，T1、T2和V，你需要求出至少要多少分钟才能击退所有的入侵者。
分析
首先二分时间，接着，就可以吧每个防御塔分成g个点，g表示在二分出的时间内可以发射多少枚导弹，然后把每个分出来的点和每个入侵者比较一下，如果这个点在二分出的时间内可以咔擦掉这个入侵者，就将它们连一条边。
然后。。。
就最大匹配一下就可以啦！
最大匹配可以用网络流或者匈牙利，如果不嫌麻烦的话就用网络流吧。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
using namespace std;
double t1,t2,v,a[60][60],lf[60][3],xhm[60][3];
int n,m,tot,next[800000],to[800000],last[1000000],xyl[800000];
bool used[800000];
double dis(double x,double y,double x1,double y1)
{
return sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
}
int bj(int x,int y)
{
next[++tot]=last[x];
last[x]=tot;
to[tot]=y;
}
bool find(int x)
{
int i,j,k,l;
for(i=last[x];i;i=next[i])
{
j=to[i];
if(!used[j])
{
used[j]=true;
if(xyl[j]==0 || find(xyl[j]))
{
xyl[j]=x;
return true;
}
}
}
return false;
}
bool ddx(double limit)
{
int i,j,k,l;
double cs=(limit-t1)/(t1+t2)+1;
tot=0;
memset(to,0,sizeof(to));
memset(last,0,sizeof(last));
memset(next,0,sizeof(next));
for(i=1;i<=n;i++)
for(j=0;j<int(cs);j++)
{
double time=j*(t1+t2)+t1;
for(k=1;k<=m;k++)
{
if(time+a[i][k]<=limit)
{
bj(int(n*j+i),int(cs*n+k));
bj(int(cs*n+k),int(n*j+i));
}
}
}
int ans=0;
memset(xyl,0,sizeof(xyl));
for(i=1;i<=int(n*cs+m);i++)
{
memset(used,0,sizeof(used));
if(find(i)) ans++;
}
return ans==m*2;
}
double rf()
{
double l=0,r=50000,mid;
int i,j,k;
for(i=1;i<=50;i++)
{
mid=(l+r)/2;
if(ddx(mid)) r=mid;
else l=mid;
}
return r;
}
int main()
{
scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&v);
t1=t1/60;
int i,j,k,l,x,y;
for(i=1;i<=m;i++)
{
scanf("%lf%lf",&xhm[i][1],&xhm[i][2]);
}
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&lf[i][1],&lf[i][2]);
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
a[i][j]=dis(lf[i][1],lf[i][2],xhm[j][1],xhm[j][2])/v;
}
double ans;
ans=rf();
printf("%.6lf",ans);
}