不错的思想
/*
大致题意： 用n个导弹发射塔攻击m个目标。每个发射架在某个时刻只能为
一颗导弹服务，发射一颗导弹需要准备t1的时间，一颗导弹从发
射到击中目标的时间与目标到发射架的距离有关。每颗导弹发
射完成之后发射架需要t2的时间进入下个发射流程。现在问
最少需要多少时间可以击毁所有m个目标。 大致思路：
二分枚举这个最大时间的最小值，每次按照这个枚举的时间构出
二分图，求最大匹配来判定枚举值是否符合要求。 注意单位，T1要除于60转化成分的 */ #include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
const double eps=1e-;
const int MAXN=;
int linker[MAXN];
bool used[MAXN];
vector<int>g[];
int uN;
bool dfs(int u)
{
for(int i=;i<g[u].size();i++)
{
if(!used[g[u][i]])
{
used[g[u][i]]=true;
if(linker[g[u][i]]==-||dfs(linker[g[u][i]]))
{
linker[g[u][i]]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int u;
int res=;
memset(linker,-,sizeof(linker));
for(u=;u<uN;u++)
{
memset(used,false,sizeof(used));
if(dfs(u))res++;
}
return res;
} int N,M;
double T1,T2,V;
struct Node
{
int x,y;
};
Node node1[],node2[];
double d[][];
double tt[MAXN][]; double dis(Node a,Node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} void init()
{
for(int i=;i<N;i++)
for(int j=;j<M;j++)
d[i][j]=dis(node1[i],node2[j]);
for(int k=;k<M;k++)
for(int i=;i<N;i++)
for(int j=;j<M;j++)
{
tt[i*M+k][j]=k*T2+(k+)*T1+d[i][j]/V;
}
uN=M;
} double solve()
{
double l=;
double r=200000000000.0;
double mid;
while(r-l>=eps)
{
mid=(l+r)/;
for(int i=;i<M;i++)g[i].clear();
for(int i=;i<M*N;i++)
for(int j=;j<M;j++)
{
if(tt[i][j]<=mid)g[j].push_back(i);
}
if(hungary()==M)
{
r=mid;
}
else l=mid;
}
printf("%.6lf\n",r);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d%d%lf%lf%lf",&N,&M,&T1,&T2,&V)!=EOF)
{
T1/=;//这个注意，没有除一直得不到答案，纠结
for(int i=;i<M;i++)scanf("%d%d",&node2[i].x,&node2[i].y);
for(int i=;i<N;i++)scanf("%d%d",&node1[i].x,&node1[i].y);
init();
solve();
}
return ;
}