1 条题解
-
0赵青海 (huhe) LV 7 SU @ 2021-8-8 10:44:37
C++ :
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #include<cmath> using namespace std; const int maxn=50+10; struct Node { int x,y; Node() {} Node(int a,int b):x(a),y(b) {} } def[maxn],ta[maxn]; int vis[maxn*maxn],pre[maxn*maxn]; double times[maxn][maxn]; double t1,t2,V; vector<int >G[maxn]; int n,m; bool DFS(int u) { for(int i=0; i<G[u].size(); i++) { int v=G[u][i]; if(vis[v]) continue; vis[v]=1; if(pre[v]==0||DFS(pre[v])) { pre[v]=u; return true; } } return false; } bool judge(double mid) { for(int i=1; i<=m; i++) G[i].clear(); for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) { double now=0; for(int k=0; k<=m; k++) { now=k*(t1+t2); if(mid-(now+t1+times[i][j])>1e-7) { G[i].push_back(j*(m+1)+k-m-1); } else break; } } memset(pre,0,sizeof(pre)); for(int i=1; i<=m; i++) { memset(vis,0,sizeof(vis)); if(!DFS(i)) return false; } return true; } int main() { cin>>n>>m>>t1>>t2>>V; t1/=60.0; for(int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); ta[i]=Node(x,y); } for(int i=1; i<=n; i++) { int x,y; scanf("%d%d",&x,&y); def[i]=Node(x,y); } for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) times[i][j]=sqrt((ta[i].x-def[j].x)*(ta[i].x-def[j].x)+(ta[i].y-def[j].y)*(ta[i].y-def[j].y))/V; double l=0,r=1000000,ans=r; while(r-l>1e-9) { double mid=(l+r)/2.0; if(judge(mid)) ans=min(ans,mid),r=mid; else l=mid; } printf("%.6lf\n",ans); }
- 1
信息
- ID
- 284
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 5
- 已通过
- 4
- 上传者