首页 > 代码库 > ZOJ3156_Taxi(二分图/二分构图)
ZOJ3156_Taxi(二分图/二分构图)
解题报告
题意:
n个人,m辆车,给出人和车的坐标,还有人的速度,求全部人都坐上车的最小时间。(一辆车只能做一个人)
思路:
原本以为在二分图上求最小的时间就变成了求二分图的最佳匹配,其实可以二分时间,满足时间的人和车连线构图,这样二分的求最小时间。
可能写挫了,我竟然这样二分时间,,,sad
其实只要把所有的可能时间存下在二分时间更快。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。