2011 国赛B答案 个人计算版

Tobielf

楼主HIT大牛！
" t' z) p( {5 l先YM，再膜拜，最后讨论：
第一问第一小问一样
第一问第二小问， 我用匈牙利跑完的结果和你一样，求出了最大权的最小值
然后又用KM算法求了一次最佳匹配，使得总开销最小
因为：从匈牙利跑完的结果来看
12点封锁12点，13点去封锁23点明显更合理一些
我们组的结果：（Police Station:表示平台，MainRoad:表示要封锁路口，cost的单位是[百米]，换算成时间直接除10即可）
* A2 D/ F. ~) \Police Station:12        MainRoad:12        Cost is:0.00
& w% H/ |/ Q4 e0 @+ S5 O6 t8 jPolice Station:16        MainRoad:14        Cost is:67.42
Police Station:9        MainRoad:16        Cost is:15.33
  E1 {+ ^8 A7 hPolice Station:14        MainRoad:21        Cost is:32.65
# j, P" U' l/ J+ u) y) {  A1 m9 RPolice Station:10        MainRoad:22        Cost is:77.08
( ?, \: J6 \# g& `0 ~+ e4 R) xPolice Station:13        MainRoad:23        Cost is:5.00
Police Station:11        MainRoad:24        Cost is:38.05
Police Station:15        MainRoad:28        Cost is:47.52
2 @' V2 S; C9 \9 i' O: gPolice Station:7        MainRoad:29        Cost is:80.15
) y3 V; ^0 H8 K3 ?; W" H5 w% \4 _Police Station:8        MainRoad:30        Cost is:30.61
Police Station:2        MainRoad:38        Cost is:39.82
$ i1 F: U+ d1 Z0 EPolice Station:5        MainRoad:48        Cost is:24.76
Police Station:4        MainRoad:62        Cost is:3.50
4 A" O, e+ }3 }+ r7 }Total:461.89
8 C4 i" k& t4 `. h( OMinium Maxium Cost is:80.15
! }- e5 O% n9 G2 p0 b第一问第三小问
3 ]6 U8 e  m6 R8 d. C- A5 i# v我们引入了一个工作量因子来衡量，同时保证出警时间为3分钟内
. f% o9 M' y( n: S' e9 nDefine:平台工作量=sigma(平台到辖区内各点发案率*平台到辖区内各点距离)
' S- W, m* T' U& h% i" ]6 I并加入动态规划思想，尽量调整各点工作量（而不是贪心）
6 w2 A( b, a8 P& f4 H2 `! n5 F- \& X' _所以加点为：29 39 61 91
! c6 G# ^5 t4 {2 M3 E, d% [* y首先确定61 92是必须要加的，28/29选一个，38/39选一个，于是有：
6 w$ h- W' e+ B0 @3 f' e  H) f9 A% ~0 Q/ U28 38 61 92
28 39 61 92
! D. `3 \, _9 u5 i29 38 61 92
2 Y; {4 J) Q2 |. p- D29 39 61 92
四种可能加点方案，都试了一下，发现加：29 39 61 92比较好
3 [. g- Q" U7 ?" L9 [接着再在29 39 61 92加入的基础上，计算出调整后各平台的工作量
发现1 13 18 20工作量较大，在100左右
中间还有一些步骤结合图分析，决定再新加一个91点
, L; B: m9 H! W2 ?再跑一遍算法，发现1 18 20工作量明显减小，使得各点都差不多了（除了西南方13点还是很高）
再次分析，发现91至92距离在3公里内，所以考虑移出92点，没必要了
7 V$ @8 b% b' C; l$ y. A故最后结果为：29 39 61 91
第二问第一小问
不同模型 不同结果 很灵活
- r3 P. T& ^( g3 a$ x第二问第二小问
模型假设：逃离速度60KM/h
结果有点不一样
% M: l  e8 c+ u+ Y8 b8 q. c) Q你是不是忽略了一个条件：案发后3分钟接到报案，说明逃犯已经走了3分钟
6 U  [1 |3 P2 c0 l我的思路是：floyd，hungary，bfs，二分枚举答案
过几天我把理清思路再说吧，被数模搞的作息乱了。。。悲剧
! P( S( T% Y! ^; L- ~- C% B' o  r* I后天还有HNCPC

BAISEHUIYI

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

酒精

厉害！我们做的有点悲剧了！
不同的有：第一问三小问我们用了多目标评价，最后增加了29，61,39三个节点。
最后一问：我们用了博弈的方法，得出了14分钟调动28个平台对36个路口进行封锁一定能将嫌犯堵在两个节点之间的结论！
悲剧了！

jerrybond6

BAISEHUIYI 发表于 2011-9-13 07:02
# g$ b; X- V3 n$ Q9 @围堵逃犯是实现最小包围圈么

当然是  在罪犯速度是60km/h时，上述方案恰好同时满足：范围最小，警力最小，时间最小 很巧合。

jerrybond6

酒精 发表于 2011-9-13 11:03
厉害！我们做的有点悲剧了！
5 C! }' C) }; y: r( b0 w! B不同的有：第一问三小问我们用了多目标评价，最后增加了29，61,39三个节点。
...

' V5 I* [/ x0 O$ P我也想过博弈搜索，极大极小剪枝，但是由于**和罪犯彼此不知道各自的搜索策略，所以我认为不能博弈，而是考虑最坏情况，以保证围堵

jerrybond6

安树庭 发表于 2011-9-13 00:10
. z* o7 C1 T( Q6 S" @! e( W我们使用穷举+仿真  我不是负责算法的同学  我把我们组的围堵思路给你看下吧

你和我思路差不多

jerrybond6

baivfhpiaqg 发表于 2011-9-13 00:16
* E" I: b0 b, ^5 J" S" S& }# [其实第五问我不明白大家的多少分钟是什么意思……
是在多少分钟把嫌疑犯抓住还是围住·····
这是俩个 ...

+ |2 m7 p$ p2 e围住那17个路口 范围太大了  不利于抓捕

jerrybond6

Tobielf 发表于 2011-9-13 05:03
楼主HIT大牛！
先YM，再膜拜，最后讨论：
第一问第一小问一样

& N5 J0 ^2 E/ {" D7 X案发后3min  考虑了

jerrybond6

Tobielf 发表于 2011-9-13 05:03
楼主HIT大牛！
% q, Q4 @2 a& w0 n# S* D先YM，再膜拜，最后讨论：
; ^# m* C7 I' A; v* z1 l6 q! u第一问第一小问一样

" S3 S/ z) z, @3 T" k9 x0 I# mhncpc 是神马 多校联合训练赛吗

jerrybond6

stuesx001 发表于 2011-9-13 01:13
! _* ?6 I, z6 o9 {9 g+ y( W2 c( f问题1：最短路，结果同楼主。。
) [/ `; x& m1 D问题2：动态最大匹配。结果全封锁最短需要时间8.0155分钟，调度方案多种， ...

" Y& Q( E: V4 K- {求教最后一问算法