2011 国赛B答案 个人计算版

Tobielf

楼主HIT大牛！
" ~1 \9 o2 l% b! I" [% E先YM，再膜拜，最后讨论：
第一问第一小问一样
; X) {" X; r% p3 E1 h0 q' w+ X第一问第二小问， 我用匈牙利跑完的结果和你一样，求出了最大权的最小值
然后又用KM算法求了一次最佳匹配，使得总开销最小
( e4 d/ M% m( X; \8 x因为：从匈牙利跑完的结果来看
! a3 X+ I. t- A8 T" v12点封锁12点，13点去封锁23点明显更合理一些
7 G9 X+ f/ G9 r  N$ u/ z& M* {% K我们组的结果：（Police Station:表示平台，MainRoad:表示要封锁路口，cost的单位是[百米]，换算成时间直接除10即可）
. y  V' @. n$ w: S: Y: r$ h0 J2 Y; _8 ePolice Station:12        MainRoad:12        Cost is:0.00
' m2 q& y( d. B3 K) ]7 W7 N8 FPolice Station:16        MainRoad:14        Cost is:67.42
Police Station:9        MainRoad:16        Cost is:15.33
% v' r  ?! C" w: ~Police Station:14        MainRoad:21        Cost is:32.65
Police Station:10        MainRoad:22        Cost is:77.08
- m" V  P! K& r  iPolice Station:13        MainRoad:23        Cost is:5.00
& T, [; j4 ^% J) OPolice Station:11        MainRoad:24        Cost is:38.05
Police Station:15        MainRoad:28        Cost is:47.52
# Z6 V7 z6 F! W8 C1 L; `Police Station:7        MainRoad:29        Cost is:80.15
6 X6 ?" {" w% N  r! iPolice Station:8        MainRoad:30        Cost is:30.61
( G7 T% a$ e5 @& |& BPolice Station:2        MainRoad:38        Cost is:39.82
Police Station:5        MainRoad:48        Cost is:24.76
5 i: K: M* B% [$ a7 X& a* uPolice Station:4        MainRoad:62        Cost is:3.50
Total:461.89
Minium Maxium Cost is:80.15
第一问第三小问
2 Q4 V( B  e. D  s: Y3 i9 {我们引入了一个工作量因子来衡量，同时保证出警时间为3分钟内
7 X" U6 v% r4 R" KDefine:平台工作量=sigma(平台到辖区内各点发案率*平台到辖区内各点距离)
并加入动态规划思想，尽量调整各点工作量（而不是贪心）
所以加点为：29 39 61 91
4 D4 f8 J& f4 l/ S* }首先确定61 92是必须要加的，28/29选一个，38/39选一个，于是有：
28 38 61 92
1 k) ?7 `2 d5 X4 [7 [5 B28 39 61 92
29 38 61 92
29 39 61 92
0 t3 T' p& Y1 _; \  O四种可能加点方案，都试了一下，发现加：29 39 61 92比较好
接着再在29 39 61 92加入的基础上，计算出调整后各平台的工作量
" v$ i$ E: t" V# R; \7 V" X/ b发现1 13 18 20工作量较大，在100左右
# h! Z9 A1 r( G中间还有一些步骤结合图分析，决定再新加一个91点
再跑一遍算法，发现1 18 20工作量明显减小，使得各点都差不多了（除了西南方13点还是很高）
% F) f: v" W( o# V; N再次分析，发现91至92距离在3公里内，所以考虑移出92点，没必要了
故最后结果为：29 39 61 91
第二问第一小问
) l" C. e& u# w1 x+ ~不同模型 不同结果 很灵活
* d  i7 ]  q/ {. @+ T第二问第二小问
2 A8 t* M* ]1 j! y7 s8 z9 _模型假设：逃离速度60KM/h
3 e- H) k$ ~; ~# n结果有点不一样
你是不是忽略了一个条件：案发后3分钟接到报案，说明逃犯已经走了3分钟
" Y- i% y; Y# z' e- n1 Y/ C我的思路是：floyd，hungary，bfs，二分枚举答案
过几天我把理清思路再说吧，被数模搞的作息乱了。。。悲剧
后天还有HNCPC

BAISEHUIYI

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

酒精

厉害！我们做的有点悲剧了！
% f. a% i9 \/ B+ m/ y$ [6 s, r0 J不同的有：第一问三小问我们用了多目标评价，最后增加了29，61,39三个节点。
  |; D7 Y! O* x% J8 D最后一问：我们用了博弈的方法，得出了14分钟调动28个平台对36个路口进行封锁一定能将嫌犯堵在两个节点之间的结论！
. y2 ?# p  S* J" V, j( @& U悲剧了！

jerrybond6

BAISEHUIYI 发表于 2011-9-13 07:02
围堵逃犯是实现最小包围圈么

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

jerrybond6

酒精 发表于 2011-9-13 11:03
0 k4 ]$ Q* K5 u& B' F厉害！我们做的有点悲剧了！
% @  p2 w5 P7 x% U6 G& J  \3 a) y不同的有：第一问三小问我们用了多目标评价，最后增加了29，61,39三个节点。
...

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

jerrybond6

安树庭 发表于 2011-9-13 00:10
% ~* K+ A/ R9 z$ z5 \我们使用穷举+仿真  我不是负责算法的同学  我把我们组的围堵思路给你看下吧

你和我思路差不多

jerrybond6

baivfhpiaqg 发表于 2011-9-13 00:16
其实第五问我不明白大家的多少分钟是什么意思……
3 M5 x4 r* B% n: {9 z是在多少分钟把嫌疑犯抓住还是围住·····
& F0 @) B# v5 p+ U1 Q& }这是俩个 ...

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

jerrybond6

Tobielf 发表于 2011-9-13 05:03
# O) A1 C% G7 c9 i. L楼主HIT大牛！
4 Z8 c5 B# p+ g) c4 X先YM，再膜拜，最后讨论：
第一问第一小问一样

案发后3min  考虑了

jerrybond6

Tobielf 发表于 2011-9-13 05:03
' C  i) a) b/ e% I: O楼主HIT大牛！
7 p& g4 d2 L' t0 j5 `1 U7 a! g先YM，再膜拜，最后讨论：
2 G8 @7 I+ I1 m8 X第一问第一小问一样

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

jerrybond6

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

求教最后一问算法