解题报告

题意：

n个人，m辆车，给出人和车的坐标，还有人的速度，求全部人都坐上车的最小时间。（一辆车只能做一个人）

思路：

原本以为在二分图上求最小的时间就变成了求二分图的最佳匹配，其实可以二分时间，满足时间的人和车连线构图，这样二分的求最小时间。

可能写挫了，我竟然这样二分时间，，，sad

其实只要把所有的可能时间存下在二分时间更快。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define N 1000 #define M 1000 #define inf 99999999 using namespace std; int n,m,mmap[N][N],vis[N],pre[N]; struct point { double x,y; } g[N],h[N]; double _time[110][110]; double dis(point p1,point p2) { return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); } int dfs(int x) { for(int i=1; i<=m; i++) { if(!vis[i]&&mmap[x][i]) { vis[i]=1; if(pre[i]==-1||dfs(pre[i])) { pre[i]=x; return 1; } } } return 0; } int main() { int i,j; double v; while(~scanf("%d%d",&n,&m)) { memset(mmap,0,sizeof(mmap)); for(i=1; i<=n; i++) { scanf("%lf%lf",&g[i].x,&g[i].y); } for(i=1; i<=m; i++) { scanf("%lf%lf",&h[i].x,&h[i].y); } scanf("%lf",&v); double tmax=-1; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { _time[i][j]=dis(g[i],h[j])/v; if(_time[i][j]>tmax) { tmax=_time[i][j]; } } } double l=0,r=tmax; double minn=0; while(l<=r) { double mid=(l+r)/2; for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { if(_time[i][j]<=mid) mmap[i][j]=1; else mmap[i][j]=0; } } int ans=0; memset(pre,-1,sizeof(pre)); for(i=1; i<=n; i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } if(ans>=n) { minn=mid; r=mid-0.00001; } else { l=mid+0.00001; } } printf("%.2lf\n",minn); } return 0; }