2011 国赛B答案 个人计算版

Tobielf

楼主HIT大牛！
/ }: i' b/ n2 v3 g先YM，再膜拜，最后讨论：
第一问第一小问一样
5 _7 {# B6 n2 G, T2 o; r4 @第一问第二小问， 我用匈牙利跑完的结果和你一样，求出了最大权的最小值
/ l9 y) e7 h+ T' U. [然后又用KM算法求了一次最佳匹配，使得总开销最小
) f6 B* q+ O) ?; `' \6 H* k% D; D# d因为：从匈牙利跑完的结果来看
$ D2 ?8 y; t- A" n" w; S12点封锁12点，13点去封锁23点明显更合理一些
我们组的结果：（Police Station:表示平台，MainRoad:表示要封锁路口，cost的单位是[百米]，换算成时间直接除10即可）
0 G2 V7 x1 C6 z. _4 oPolice Station:12        MainRoad:12        Cost is:0.00
Police Station:16        MainRoad:14        Cost is:67.42
& F6 a6 w; ~  \Police Station:9        MainRoad:16        Cost is:15.33
Police Station:14        MainRoad:21        Cost is:32.65
9 D0 [5 {( q# n0 S5 KPolice Station:10        MainRoad:22        Cost is:77.08
# X/ O$ t, d. c4 g+ ZPolice Station:13        MainRoad:23        Cost is:5.00
: e4 ]+ v9 s& m& u7 M" f6 EPolice Station:11        MainRoad:24        Cost is:38.05
Police Station:15        MainRoad:28        Cost is:47.52
Police Station:7        MainRoad:29        Cost is:80.15
0 ?& n% W, d. O% S" cPolice Station:8        MainRoad:30        Cost is:30.61
! |& m" P: w4 N4 e7 D/ l2 G/ P5 c9 {Police Station:2        MainRoad:38        Cost is:39.82
4 `( J5 O& R0 k! ~- t' [4 sPolice Station:5        MainRoad:48        Cost is:24.76
8 U0 Y* U  `$ k( E1 ]Police Station:4        MainRoad:62        Cost is:3.50
Total:461.89
. I" l4 {- x) D, |Minium Maxium Cost is:80.15
第一问第三小问
我们引入了一个工作量因子来衡量，同时保证出警时间为3分钟内
Define:平台工作量=sigma(平台到辖区内各点发案率*平台到辖区内各点距离)
' ^: g6 [/ P4 y7 S4 n  r并加入动态规划思想，尽量调整各点工作量（而不是贪心）
所以加点为：29 39 61 91
首先确定61 92是必须要加的，28/29选一个，38/39选一个，于是有：
28 38 61 92
! ?$ f8 j" u) I8 t" _& U( Q28 39 61 92
! Q, T6 b9 z: O$ G! c/ @& z29 38 61 92
29 39 61 92
) d& B0 n% ~7 E8 ~- L* x四种可能加点方案，都试了一下，发现加：29 39 61 92比较好
" j" k0 V, y! G) R接着再在29 39 61 92加入的基础上，计算出调整后各平台的工作量
发现1 13 18 20工作量较大，在100左右
1 D8 E/ D0 ], ^) S( b中间还有一些步骤结合图分析，决定再新加一个91点
再跑一遍算法，发现1 18 20工作量明显减小，使得各点都差不多了（除了西南方13点还是很高）
2 F$ U1 n6 [7 w4 y) x4 z再次分析，发现91至92距离在3公里内，所以考虑移出92点，没必要了
故最后结果为：29 39 61 91
  i* Z- C9 J. Z  u' R& L6 G  m  u第二问第一小问
不同模型 不同结果 很灵活
第二问第二小问
模型假设：逃离速度60KM/h
6 S( e  Z# J. W) W3 d3 }$ E结果有点不一样
你是不是忽略了一个条件：案发后3分钟接到报案，说明逃犯已经走了3分钟
我的思路是：floyd，hungary，bfs，二分枚举答案
( q6 }% `* m. `% p  Z3 a- ]过几天我把理清思路再说吧，被数模搞的作息乱了。。。悲剧
后天还有HNCPC

BAISEHUIYI

围堵逃犯是实现最小包围圈么

酒精

厉害！我们做的有点悲剧了！
1 v' I' y  K- r% K不同的有：第一问三小问我们用了多目标评价，最后增加了29，61,39三个节点。
6 b$ e" [; |/ N3 b  d/ `/ l/ H0 E最后一问：我们用了博弈的方法，得出了14分钟调动28个平台对36个路口进行封锁一定能将嫌犯堵在两个节点之间的结论！
悲剧了！

jerrybond6

BAISEHUIYI 发表于 2011-9-13 07:02
4 [% g) {* y  A5 b围堵逃犯是实现最小包围圈么

! Z! F. Y$ {! O0 c- d. I当然是  在罪犯速度是60km/h时，上述方案恰好同时满足：范围最小，警力最小，时间最小 很巧合。

jerrybond6

酒精 发表于 2011-9-13 11:03
厉害！我们做的有点悲剧了！
& v2 ]  j% {2 V8 w. v  l不同的有：第一问三小问我们用了多目标评价，最后增加了29，61,39三个节点。
...

) T$ R4 X; E" G% m5 G6 u. m我也想过博弈搜索，极大极小剪枝，但是由于**和罪犯彼此不知道各自的搜索策略，所以我认为不能博弈，而是考虑最坏情况，以保证围堵

jerrybond6

安树庭 发表于 2011-9-13 00:10
我们使用穷举+仿真  我不是负责算法的同学  我把我们组的围堵思路给你看下吧

你和我思路差不多

jerrybond6

baivfhpiaqg 发表于 2011-9-13 00:16
其实第五问我不明白大家的多少分钟是什么意思……
$ T$ ^3 o+ z7 T, q是在多少分钟把嫌疑犯抓住还是围住·····
! J" K5 e0 Q$ u( H5 c6 y这是俩个 ...

围住那17个路口 范围太大了  不利于抓捕

jerrybond6

Tobielf 发表于 2011-9-13 05:03
# |+ h/ ~7 F. P0 M! g; b楼主HIT大牛！
先YM，再膜拜，最后讨论：
( Y& k" m& v; n1 `$ E: D% T$ [第一问第一小问一样

- A# ?8 i8 ]( H+ b" Y7 P/ E案发后3min  考虑了

jerrybond6

Tobielf 发表于 2011-9-13 05:03
, m# d2 X$ c3 V4 {: z楼主HIT大牛！
先YM，再膜拜，最后讨论：
4 L% i: r  X3 l第一问第一小问一样

hncpc 是神马 多校联合训练赛吗

jerrybond6

stuesx001 发表于 2011-9-13 01:13
问题1：最短路，结果同楼主。。
问题2：动态最大匹配。结果全封锁最短需要时间8.0155分钟，调度方案多种， ...

求教最后一问算法