1 条题解

  • 0
    @ 2025-4-12 21:36:07

    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
    上传者