1 条题解
-
0
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; }
- 1
信息
- ID
- 876
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者