自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 23:02:42，当前版本为作者最后更新于2024-09-16 14:05:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：匈牙利算法（二分图最大匹配），如果不会欢迎阅读我写的另一篇题解。

对于本题来说，因为导弹防御塔与入侵者并不是一一对应（一个导弹防御塔）可以对应若干个敌人，那么考虑将一个导弹防御塔拆成若干个结点。

而多少个结点取决于总用时（即答案），发现答案满足单调性（因为如果能在某一时间内击退敌人，那么时间更长也一定可以），那么可以用二分答案，再用二分的 $mid$ 来拆点（导弹防御塔）。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=200+9;
const double eps=1e-9;
vector<int>g[maxn];
int n,m,t,ans,match[maxn*maxn];
double t1,t2,v,dis[maxn][maxn],l=0.0,r=1e6;
pair<int,int>a[maxn],b[maxn];
bitset<maxn*maxn>vis;
inline bool dfs(const int u){
	for(int v:g[u])if(!vis[v]){
		vis[v]=true;
		if(!match[v]||dfs(match[v])){match[v]=u;return true;}
	}
	return false;
}
inline bool check(const double lim){
	const int num=min(m,int((lim+t2)/(t1+t2)+eps*0.01));
	//cerr<<"[stderr]"<<fixed<<setprecision(8)<<lim<<' '<<num<<endl;
	for(int i=1;i<=m;i++){
		g[i].clear();
		for(int j=1;j<=n;j++)for(int k=1;k<=num;k++)
            if(dis[i][j]+t1*k+t2*(k-1)<=lim)g[i].push_back((j-1)*num+k);
	}
	memset(match,0,sizeof match);
	for(int i=1;i<=m;i++){
		//cerr<<"[stderr]"<<i<<endl;
		vis.reset();
		if(!dfs(i))return false;
	}
	return true;
}
signed main(){
	// freopen("dat.in","r",stdin);
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>t1>>t2>>v,t1/=60.0;
	for(int i=1,x,y;i<=m;i++)cin>>a[i].first>>a[i].second;
	for(int i=1,x,y;i<=n;i++)cin>>b[i].first>>b[i].second;
	for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)
            dis[i][j]=sqrt(double(a[i].first-b[j].first)*(a[i].first-b[j].first)+double(a[i].second-b[j].second)*(a[i].second-b[j].second))/v;
	for(double mid=(l+r)/2.0;r-l>eps;mid=(l+r)/2.0)
		if(check(mid))r=mid;
		else l=mid;
	cout<<fixed<<setprecision(6)<<r<<endl;
	//for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cerr<<fixed<<setprecision(2)<<dis[i][j]<<' ';cerr<<endl;}
}