思路
寻找最小值,想到二分
利用二分出的mid进行建立二分图(左边为侵略者,右边是在mid时间内可以到达目的地的导弹),
判断该二分图的最大匹配是否是完备匹配
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 54;
int n,m,v[N*N],f[N*N];
double t1,t2,V,dist[N][N];
const double eps = 1e-8;
struct{int x,y;}a[N],b[N];
vector<int>e[N];
bool dfs(int x){
for(int i = 0;i < e[x].size();i++){
int y = e[x][i];
if(!v[y]){
v[y] = 1;
if(f[y] == -1 || dfs(f[y])){
f[y] = x;
return true;
}
}
}
return false;
};
bool judge(double mid){
memset(f,-1,sizeof(f));
int p = (mid+t2)/(t1+t2);
p = min(p,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++)
if(dist[i][j] + k*t1 + (k-1)*t2 <= mid)
e[i].push_back((j-1)*p+k);
}
for(int i = 1;i <= m;i++){
memset(v,0,sizeof(v));
if(!dfs(i))return false;
}
return true;
};
int main(){
cin>>n>>m>>t1>>t2>>V;
t1 /= 60;
for(int i = 1;i <= m;i++)cin>>a[i].x>>a[i].y;
for(int i = 1;i <= n;i++)cin>>b[i].x>>b[i].y;
for(int i = 1;i <= m;i++)
for(int j = 1;j <= n;j++)
dist[i][j] = sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y))/V;
double l = 0,r = 1e8;
while(r -l > eps){
double mid = (l+r) /2;
if(judge(mid))r = mid;
else l = mid;
}
printf("%.6f\n",l);
}