/ CWOI / 题库 /

2017.07.17 P3 男女匹配

2017.07.17 P3 男女匹配

题目描述

在一个有障碍的网格图中,有 male 个男人和 female 个女人,还有一个叫 BOSS 的人妖(既可以当男人又可以当女人)。这些人分布在地图上,每一个 cell(房间)可以同时有多个人。这些人每个人移动各需要 \(t_i\) 的时间,问最小需要多长时间,使得每一个人都可以和异性单独待在同一个房间里?

输入格式

在 n \(\times\) m的地图上,'.' 表示一个 free room ,既可以移动到或者经过的房间;'#' 表示一个障碍物单位,既不可达也不可经过。
第一行为四个整数,n, m, male, female,分别表示地图的行数,列数,男性和女性的个数。
接下来 n 行描述一个地图,表示是否可达。
接下来 1 行描述 BOSS(人妖),x, y, t,表示这个人所在的坐标和移动一个单位所需的时间。
接下来的 male 行和 female 行分别描述男人和女人所在的坐标和移动一个单元格所需时间,格式同上。

输出格式

输出最小时间,使得每个人都可以和异性单独呆在同一个房间里(同一个房间只能有一对人),如果不行,输出 -1。

样例1

输入

4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2

输出

2

样例2

输入

2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2

输出

-1

数据范围

对于 50%的数据,1 \(\leq\) n, m \(\leq\) 11, 0 \(\leq\) males, females \(\leq\) n \(\times\) m, 1 \(\leq\) r \(\leq\) n, 1 \(\leq\) c \(\leq\) m, 1 \(\leq\) t \(\leq\) \(10^9\);
对于 100%的数据,1 \(\leq\) n, m \(\leq\) 22, 0 \(\leq\) males, females \(\leq\) n \(\times\) m, 1 \(\leq\) r \(\leq\) n, 1 \(\leq\) c \(\leq\) m, 1 \(\leq\) t \(\leq\) \(10^9\)。

限制

3s

样例解释

样例 1:BOSS的位置在(2, 1),移动到相邻 cell 时间为 1,一女的位置在 (1, 1),移动时间 2,其他 2 男 2 女的位置在(2, 1),移动时间 2。让 BOSS 和一女从 (1, 1) 移动到 (1, 2),所需时间为 2,让一男一女从 (2, 1) 移动 (1, 1),所需时间为 2,最后一对男女不需要移动。

来源

Codeforces513F2
CWOI新高二专题测试十四

信息

难度
4
分类
图结构 | 网络流搜索 | 二分查找 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者