栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3460 Missile

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3460 Missile

#include<stdio.h>#include<vector>#include<math.h>#include<memory.h>#define MAXN 50*50using namespace std;struct Point {double x, y;} p[55], q[55];int n, m, i, j, K;double t1, t2, V;double d[55][55];double dist(Point a, Point b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}int mat[MAXN], tmat[MAXN];int g[50 * 50 + 10][55];int N, M;int hungry_aug(int i) {int v, j;for (j = 0; j < M; j++)if (g[i][j] && tmat[j] == 0) {tmat[j] = 1;v = mat[j];mat[j] = i;if (v == -1 || hungry_aug(v))return 1;mat[j] = v;}return 0;}int hungry() {int i, k = 0;memset(mat, -1, sizeof(mat));for (i = 0; i < N; i++) {memset(tmat, 0, sizeof(tmat));k += hungry_aug(i);}return k;}int main() {while (scanf("%d%d%lf%lf%lf", &n, &m, &t1, &t2, &V) != EOF) {t1 /= 60;for (i = 1; i <= m; i++) {scanf("%lf%lf", &q[i].x, &q[i].y);}for (i = 1; i <= n; i++) {scanf("%lf%lf", &p[i].x, &p[i].y);}for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)d[i][j] = dist(p[i], q[j]) / V;double l = 0, r = 100000, mid;int tim = 50;while (tim--) {mid = (l + r) * 0.5;memset(g, 0, sizeof(g));for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)for (K = 0; K < m; K++) {if (K * (t1 + t2) + t1 + d[i][j] <= mid) {g[(i - 1) * m + K + 1-1][j-1] = 1;}}N = n * m;M = m;int res = hungry();if (res >= m) {r = mid;} elsel = mid;}printf("%.6lfn", mid);}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/376546.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号