[二分匹配]zoj 3156：Taxi

大致题意：
    有n个人和m辆车(n<=m)。给出所有人和车的坐标，以及人移动的速度。现在让每个人走去找一辆车坐。每辆车只能乘坐一个人，花费的时间最少是多少。

 

大致思路：
    二分这个时间的最大值tmax，再用匈牙利算法判定是否n个人都能在tmax的时间内赶到车上。

    一开始直接二分距离，高精度神马的写渣了。后来发现，二分枚举距离值的下标就可以~~

 

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int nMax=200;
const double eps=1e-9;
int n,m;
bool map[nMax][nMax];
bool vis[nMax];
int linkk[nMax];
int dfs(int s){
	for(int i=1;i<=m;i++){
			if(!vis[i]&&map[s][i]){
				vis[i]=1;
		        if(linkk[i]==-1||dfs(linkk[i])){
						linkk[i]=s;
			             return 1;
				}
			}
	}
	return 0;
}

double peo[nMax][2];
double tex[nMax][2];
double dis[nMax][nMax],vec;

double getdis(int a,int b)
{
    double tmp=(peo[a][0]-tex[b][0])*(peo[a][0]-tex[b][0])+(peo[a][1]-tex[b][1])*(peo[a][1]-tex[b][1]);
    double res=sqrt(tmp);
    return res;
}

double tim[200000];
int xxx;
double getinit()
{
    xxx=0;
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            dis[i][j]=getdis(i,j);
            dis[i][j]/=vec;
            tim[xxx++]=dis[i][j];
        }
    }
}

bool check(double mid)
{
    int i,j;
  //  memset(map,0,sizeof(map));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(abs(dis[i][j]-mid)<eps||dis[i][j]<mid)
            {
                map[i][j]=1;
            }
            else
            {
                map[i][j]=0;
            }
        }
    }
    int res=0;
    memset(linkk,-1,sizeof(linkk));
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))res++;
    }
    if(res==n)return 1;
    return 0;
}

int main()
{
    int i,j,v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
          // cin>>peo[i][0]>>peo[i][1];
             scanf("%lf%lf",&peo[i][0],&peo[i][1]);
        }
        for(i=1;i<=m;i++)
        {
           // cin>>tex[i][0]>>tex[i][1];
            scanf("%lf%lf",&tex[i][0],&tex[i][1]);
        }
        cin>>vec;
        getinit();
        sort(tim,tim+xxx);
        int left=0,right=xxx-1,mid,ans=xxx-1;
        while(right>=left){
            mid=(right+left)/2;
            if(check(tim[mid])){
                right=mid-1;
                if(mid<ans)ans=mid;
            }
            else{
                left=mid+1;
            }
        }
        printf("%.2f\n",tim[ans]);
    }
    return 0;
}