求帮看为什么RE
  • 板块学术版
  • 楼主algorith
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/25 19:24
  • 上次更新2023/10/23 20:30:56
查看原帖
求帮看为什么RE
302888
algorith楼主2023/3/25 19:24
#include<bits/stdc++.h>
using namespace std;
const int N=6005,M=1e6+10;
int n,m,t2,v,qx[N],qy[N],fx[N],fy[N],vis[N],lk[N],to[M],nxt[M],head[N],tot=0;double t1,dis[N][N];
void add(int x,int y){
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
bool xzy(int x){
	for(int i=head[x];i;i=nxt[i]){
		int u=to[i];
		if(!vis[u]){
			vis[u]=1;
			if(!lk[u]||xzy(lk[u])){
				lk[u]=x;
				return 1;
			}
		}
	}
	return 0;
}
bool check(double x){
	for(int i=1;i<=m;++i){
		memset(vis,0,sizeof vis);
		if(!xzy(i))return 0;
	}
	return 1;
}
int main(){
	cin>>n>>m>>t1>>t2>>v;t1/=60;
	for(int i=1;i<=m;++i)cin>>qx[i]>>qy[i];
	for(int i=1;i<=n;++i){
		cin>>fx[i]>>fy[i];
		for(int j=1;j<=m;++j)
			dis[i][j]=sqrt((fx[i]-qx[j])*(fx[i]-qx[j])*1.0+(fy[i]-qy[j])*(fy[i]-qy[j]));
	}
	double l=0,r=1e6,eps=1e-7;
	while(r-l>eps){
		tot=0;
		memset(head,0,sizeof head);
		memset(lk,0,sizeof lk);
		double mid=(l+r)/2;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				for(int k=1;k<=m;++k)
					if(dis[i][k]/v+(j-1)*(t1+t2)+t1<=mid)
						add(k,i*m+j+m);
		if(check(mid))r=mid;
		else l=mid;
	}
	cout<<fixed<<setprecision(6)<<l;
	return 0;
}

站外题,导弹防御塔

2023/3/25 19:24
加载中...