2220 - 可恶的雾霾天
最近雾霾侵袭，小明出门都带上口罩了。有一天小明出门办事，办完事后发现雾霾天愈发严重，于是他想马上坐出租车回家。
他发现附近有n个人要坐出租车，并且有m辆出租车停在附近等着拉客。每个人的步行速度都是v，现在给你n个人和m辆出租车的位置，请你计算出所有人都坐上出租车最少需要多长时间。注意一辆出租车只能坐一个人。
Input
输入包含多组测试数据。
每组输入的第一行是两个整数n（0<n<=100）和m（n<=m<=100）。
接下来n行，每行输入两个整数Xi和Yi（0<=Xi,Yi<=10000），表示第i个人的位置。
然后再输入m行，每行输入两个整数xi和yi（0<=xi,yi<=10000），表示第i辆出租车的位置。
最后输入一个实数v（0.00001<v<=10000），表示每个人的步行速度。
Output
对于每组输入，输出所有人都坐上出租车最少需要多长时间，结果保留两位小数。
Examples
Input
2 3 0 0 0 1 1 0 1 1 2 1 1
Output
1.00
Solution C++
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define MAXN 100 #define inf 1000000000 #define _clr(x) memset(x,0xff,sizeof(int)*MAXN) double g[MAXN][MAXN]; int match1[MAXN], match2[MAXN]; int hungary(int m, int n, int mat[][MAXN], int *match1, int *match2) { int s[MAXN], t[MAXN], p, q, ret = 0, i, j, k; for (_clr(match1),_clr(match2), i = 0; i < m; ret += (match1[i++] >= 0)) for (_clr(t),s[p = q = 0] = i; p <= q && match1[i] < 0; p++) for (k = s[p], j = 0; j < n && match1[i] < 0; j++) if (mat[k][j] && t[j] < 0) { s[++q] = match2[j]; t[j] = k; if (s[q] < 0) for (p = j; p >= 0; j = p) { match2[j] = k = t[j]; p = match1[k]; match1[k] = j; } } return ret; } int main() { int n, m, i, j, k, left, right, mid, map[MAXN][MAXN]; double px[MAXN], py[MAXN], tx[MAXN], ty[MAXN], v, time[MAXN*MAXN], T; while (scanf("%d%d", &n, &m) != EOF) { for (i = 0; i < n; i++) scanf("%lf%lf", &px[i], &py[i]); for (i = 0; i < m; i++) scanf("%lf%lf", &tx[i], &ty[i]); scanf("%lf", &v); for (k = i = 0; i < n; i++) for (j = 0; j < m; j++) { g[i][j] = sqrt((px[i] - tx[j]) * (px[i] - tx[j]) + (py[i] - ty[j]) * (py[i] - ty[j])) / v; time[k++] = g[i][j]; } sort(time, time + k); left = 0; right = k; while (left < right) { mid = (left + right) >> 1; memset(map, 0, sizeof(map)); for (i = 0; i < n; i++) for (j = 0; j < m; j++) if (g[i][j] <= time[mid]) map[i][j] = 1; if (hungary(n, m, map, match1, match2) == n) { T = time[mid]; right = mid; } else left = mid + 1; } printf("%.2lf\n", T); } return 0; }